「BZOJ1954」Pku3764 The xor – longest Path
Description
给定一棵n个点的带权树，求树上最长的异或和路径
Input
The input contains several test cases. The first line of each test case contains an integer n(1<=n<=100000), The following n-1 lines each contains three integers u(0 <= u < n),v(0 <= v < n),w(0 <= w < 2^31), which means there is an edge between node u and v of length w.
Output
For each test case output the xor-length of the xor-longest path.
Sample Input
4
1 2 3
2 3 4
2 4 6
1 2 3
2 3 4
2 4 6
Sample Output
7
HINT
The xor-longest path is 1->2->3, which has length 7 (=3 ⊕ 4)
注意：结点下标从1开始到N….
题解
求出根到每个结点的边权异或和
问题转换为任选两点，异或和最大
trie的经典？应用
在trie上从插入所有权值，再查询每个权值。。。（从高位到低位）
查询x的时候，每一位尽量走与x该位不同的结点
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> #define ll long long #define inf 2000000000 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int bin[35]; int n,ans,cnt; int val[100005],last[100005]; struct edge{ int to,next,v; }e[200005]; struct trie{ int cnt; int ch[3000005][2]; void insert(int x){ int now=0; for(int i=30;i>=0;i--) { int t=x&bin[i];t>>=i; if(!ch[now][t])ch[now][t]=++cnt; now=ch[now][t]; } } void query(int x){ int tmp=0,now=0; for(int i=30;i>=0;i--) { int t=x&bin[i];t>>=i; if(ch[now][t^1])now=ch[now][t^1],tmp+=bin[i]; else now=ch[now][t]; } ans=max(tmp,ans); } }trie; void insert(int u,int v,int w) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w; } void dfs(int x,int fa) { for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa) { val[e[i].to]=val[x]^e[i].v; dfs(e[i].to,x); } } int main() { bin[0]=1;for(int i=1;i<=30;i++)bin[i]=bin[i-1]<<1; n=read(); for(int i=1;i<n;i++) { int u=read(),v=read(),w=read(); insert(u,v,w); } dfs(1,0); for(int i=1;i<=n;i++) trie.insert(val[i]); for(int i=1;i<=n;i++) trie.query(val[i]); printf("%d",ans); return 0; } |
Subscribe
计数器 9787730
OI 课件=>
OI 课件=>