The xor-longest path is 1->2->3, which has length 7 (=3 ⊕ 4) 注意：结点下标从1开始到N....
因为这道题求的是树上的最大异或和路径。我们知道对于树上路径，要么是一条链，要么是对于一个节点的两个不同的子链。 我们记录树上每个点到根节点的亦或和。对于每个异或和的二进制建一颗trie树。 然后贪心，从trie根节点向下，尽量使跑到的边和原本的异或和不同，因为这样它们再次亦或才最大。 #include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #define REP(i,k,n) for(int i=k;i<=n;i++) #define in(a) a=read() #define MAXN 300010 using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } queue <int> Q; int n,cnt=0,ans; int vis[MAXN],sum[MAXN]; int tree[6333333][2]; int total=0,head[MAXN],nxt[MAXN],to[MAXN],val[MAXN]; inline void adl(int a,int b,int c){ total++; to[total]=b; val[total]=c; nxt[total]=head[a]; head[a]=total; return ; } inline void bfs(){ Q.push(1); vis[1]=1; while(!Q.empty()){ int u=Q.front(); Q.pop(); for(int e=head[u];e;e=nxt[e]) if(!vis[to[e]]){ vis[to[e]]=1; sum[to[e]]=sum[u]^val[e]; Q.push(to[e]); } } return ; } inline void insert(int x){ int u=0; for(int i=30;i>=0;i--){ int t=x&(1<<i); t=(t>>i); if(!tree[u][t]) tree[u][t]=++cnt; u=tree[u][t]; } return ; } inline int query(int x){ int u=0,tmp=0; for(int i=30;i>=0;i--){ int t=x&(1<<i); t=(t>>i); if(tree[u][t^1]) u=tree[u][t^1],tmp+=(1<<i); else u=tree[u][t]; } return tmp; } int main(){ in(n); int a,b,c; REP(i,1,n-1) in(a),in(b),in(c),adl(a,b,c),adl(b,a,c); bfs(); REP(i,1,n) insert(sum[i]); REP(i,1,n){ ans=max(ans,query(sum[i])); } cout<<ans; return 0; }
转载于:https://www.cnblogs.com/jason2003/p/9747688.html
