本文共 2255 字，大约阅读时间需要 7 分钟。
一个很经典的套路 思想是 F [u,v] = F[1,u] ^ F[1,v]
这样就转化成了n个数两两异或 求最大值 可以用字典树来做 每次用当前数去树中寻求最大xor值 然后把这个数字插进去 就相当于这个数字和之前所有的数字都比较了
发现自从学习了kdtree等一群数据结构之后...写什么都想学线段树的写法..好像很不错啊..?
#include #include #include #include #include #include #include #include #include using namespace std;#define L long long#define pb push_backconst L maxn = 100050 ;L n ;vector q[maxn] ;vector w[maxn] ;L f[maxn] ;bool vis[maxn] ;void bfs(L u) { queue que ; que.push(u) ; que.push(0) ; while(!que.empty()) { L u = que.front() ; que.pop() ; L ff = que.front() ; que.pop() ; for(L i = 0 ; i < q[u].size() ; i ++ ){ L v = q[u][i] ; if(vis[v]) { vis[v] = false ; f[v] = ff ^ w[u][i] ; que.push(v) ; que.push(f[v]) ; } } }}L a[50] ;struct node { L l , y ;}b[35 * maxn];L cnt ;L e[50] ;L did() { L qs = 0 ; L de = 0 ; L res = 0; while(de + 1 <= 32) { L nd = de + 1 ; if(a[nd] == 1) { if(b[qs].l != -1) { res += e[nd] ; qs = b[qs].l ; } else if(b[qs].y != -1) { res += 0 ; qs = b[qs].y ; } else return res ; } else { if(b[qs].y != -1) { res += e[nd] ; qs = b[qs].y ; } else if(b[qs].l != -1) { res += 0 ; qs = b[qs].l ; } else return res ; } de = nd ; } return res ;}void inse() { L qs = 0 ; L de = 0 ; while(de + 1 <= 32) { L nd = de + 1 ; if(a[nd] == 0) { if(b[qs].l == -1) { b[qs].l = (++cnt) ; qs = b[qs].l; b[qs].l = -1 ; b[qs].y = -1 ; } else { qs = b[qs].l ; } } else { if(b[qs].y == -1) { b[qs].y = (++cnt) ; qs = b[qs].y; b[qs].l = -1 ; b[qs].y = -1 ; } else { qs = b[qs].y ; } } de = nd ; }}int main(){ while(scanf("%lld",&n) != EOF) { for(L i = 1 ; i <= n ; i ++ )q[i].clear() ; for(L i = 1 ; i <= n ; i ++ )w[i].clear() ; for(L i = 1 ; i < n ; i ++ ){ L u , v , c; scanf("%lld%lld%lld",&u,&v,&c) ; q[u].pb(v); q[v].pb(u); w[u].pb(c); w[v].pb(c); } e[32] = 1 ; for(L j = 31 ; j >= 1 ; j -- ) { e[j] = 2*e[j+1] ; } memset(vis,true,sizeof(vis)); f[1] = 0 ; vis[1] = false; bfs(1) ; cnt = 0 ; b[cnt].l = -1; b[cnt].y = -1; L ans = 0 ; for(L i = 1 ; i <= n ; i ++ ){ L x = f[i]; for(L j = 32 ; j >= 1 ; j -- ) { a[j] = x%2 ; x /= 2 ; } L res = did() ; if(ans < res) ans = res ; inse() ; } printf("%lld\n",ans) ; }}
// 好像还是第一次写字典树 ..
转载于:https://www.cnblogs.com/rayrayrainrain/p/6582392.html