首页 > 代码库 > BZOJ1954: Pku3764 The xor-longest Path
BZOJ1954: Pku3764 The xor-longest Path
题解：
在树上i到j的异或和可以直接转化为i到根的异或和^j到根的异或和。
所以我们把每个点到根的异或和处理出来放到trie里面，再把每个点放进去跑一遍即可。
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 100000+5 26 27 #define maxm 4000000+5 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 #define for4(i,x) for(int i=head[x],y;i;i=e[i].next) 43 44 #define mod 1000000007 45 46 using namespace std; 47 48 inline int read() 49 50 { 51 52 int x=0,f=1;char ch=getchar(); 53 54 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 55 56 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 57 58 return x*f; 59 60 } 61 struct edge{int go,next;ll w;}e[2*maxn]; 62 int n,tot,cnt,head[maxn],t[maxm][2]; 63 ll a[maxn]; 64 inline void insert(int x,int y,ll z) 65 { 66 e[++tot]=(edge){y,head[x],z};head[x]=tot; 67 e[++tot]=(edge){x,head[y],z};head[y]=tot; 68 } 69 inline void dfs(int x,int fa) 70 { 71 for4(i,x)if((y=e[i].go)!=fa) 72 { 73 a[y]=a[x]^e[i].w; 74 dfs(y,x); 75 } 76 } 77 inline void add(ll x) 78 { 79 int now=1; 80 for3(i,62,0) 81 { 82 int j=x>>i&1; 83 if(!t[now][j])t[now][j]=++cnt; 84 now=t[now][j]; 85 } 86 } 87 inline ll query(ll x) 88 { 89 int now=1;ll ret=0; 90 for3(i,62,0) 91 { 92 int j=x>>i&1^1; 93 if(t[now][j])ret|=(ll)1<<i;else j^=1; 94 now=t[now][j]; 95 } 96 return ret; 97 } 98 99 int main()100 101 {102 103 freopen("input.txt","r",stdin);104 105 freopen("output.txt","w",stdout);106 107 n=read();108 for1(i,n-1){int x=read(),y=read(),z=read();insert(x,y,z);}109 dfs(1,0);110 cnt=1;111 for1(i,n)add(a[i]);112 ll ans=0;113 for1(i,n)ans=max(ans,query(a[i]));114 cout<<ans<<endl;115 116 return 0;117 118 }
1954: Pku3764 The xor-longest Path
Time Limit: 1 Sec Memory Limit: 64 MBSubmit: 383 Solved: 161
[Submit][Status]
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....
Source
鸣谢陶文博
BZOJ1954: Pku3764 The xor-longest Path
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。