重庆忠县网站建设公司,用新华做网站名是否侵权,网站开发国内外研究,网业游戏大全洛谷传送门 文章目录题目描述解析代码题目描述 解析
本题关键就在于一点#xff1a; 若把每个点的深度dep[i]定义为从根到节点边权的异或和 那么i到j的路径异或和可以表示为#xff1a; dep[i] ^ dep[j] 首先要是i、j在不同子树上显然成立 如果他们在同一子树上#xff0c;…洛谷传送门
文章目录题目描述解析代码题目描述 解析
本题关键就在于一点 若把每个点的深度dep[i]定义为从根到节点边权的异或和 那么i到j的路径异或和可以表示为 dep[i] ^ dep[j] 首先要是i、j在不同子树上显然成立 如果他们在同一子树上那么它们到根的公共部分异或两遍会抵消 所以也是成立的
这样dfs一遍求出dep数组 本题就变成01trie的模板题了
代码
#includebits/stdc.h
using namespace std;
#define ll long long
typedef unsigned long long ull;
const int N 1e6100;
const int M1e75;
const int mod1e97;
int n,m;
int tr[N][3],tot1,end[N];
int fi[N],cnt-1;
struct node{int to,nxt,v;
}p[N1];
void addline(int x,int y,int v){p[cnt](node){y,fi[x],v};fi[x]cnt;
}
int dep[N];
void dfs(int x,int f){for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tof) continue;dep[to]dep[x]^p[i].v;dfs(to,x);}return;
}
int mi[33];
int s[33],k;
void build(int o){for(int i0;i30;i){s[i]omi[i]?1:0;}int p1;for(int i30;i0;i--){if(!tr[p][s[i]]) tr[p][s[i]]tot;ptr[p][s[i]];}end[p];
}int ask(int o){for(int i0;i30;i){s[i]omi[i]?1:0;}int p1,res0;for(int i30;i0;i--){int nows[i];if(tr[p][!now]){ptr[p][!now];resmi[i];}else ptr[p][now];}return res;
}
int main(){mi[0]1;for(int i1;i31;i) mi[i]mi[i-1]1;memset(fi,-1,sizeof(fi));scanf(%d,n);for(int i1;in;i){int a,b,c;scanf(%d%d%d,a,b,c);addline(a,b,c);addline(b,a,c);}dfs(1,0);for(int i1;in;i){build(dep[i]);}int ans0;for(int i1;in;i){ansmax(ans,ask(dep[i]));}printf(%d,ans);return 0;
}
/*
9 6 10
5 6 2 10 10 7 3 2 9
1 4 4 3 2 16 4 10
3 5 2 7 1 9
3 8 2 10
*/
