题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=5416 ———————————————————————————————— CRB and Tree
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 2145 Accepted Submission(s): 648
Problem Description CRB has a tree, whose vertices are labeled by 1, 2, …, N. They are connected by N – 1 edges. Each edge has a weight. For any two vertices u and v(possibly equal), f(u,v) is xor(exclusive-or) sum of weights of all edges on the path from u to v. CRB’s task is for given s, to calculate the number of unordered pairs (u,v) such that f(u,v) = s. Can you help him?
Input There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case: The first line contains an integer N denoting the number of vertices. Each of the next N - 1 lines contains three space separated integers a, b and c denoting an edge between a and b, whose weight is c. The next line contains an integer Q denoting the number of queries. Each of the next Q lines contains a single integer s. 1 ≤ T ≤ 25 1 ≤ N ≤ 105 1 ≤ Q ≤ 10 1 ≤ a, b ≤ N 0 ≤ c, s ≤ 105 It is guaranteed that given edges form a tree.
Output For each query, output one line containing the answer.
Sample Input 1 3 1 2 1 2 3 2 3 2 3 4
Sample Output 1 1 0 Hint
For the first query, (2, 3) is the only pair that f(u, v) = 2. For the second query, (1, 3) is the only one. For the third query, there are no pair (u, v) such that f(u, v) = 4.
———————————————————————————————— 题目大意： 在一棵n个节点的生成树树上,每个边有一个边权 就是定义f(u,v)为树上u->v路径上边权的异或和 , 有q次查询,每次问你在这棵树上,f()=s的情况有多少种
解题思路: 这其实是一个思维题 通过遍历我们能够知道每一个点到根节点路径上的异或和 因为异或运算满足消去律,所以f(1,u)^f(1,v)=f(u,v);
通过这些我们就好计算了, 只要一遍dfs预处理出每个点到根节点的f(),hash一下 , 最后计算就行
注意一下 0的情况就行了
附本题代码 —————————————————————————————————————————————————
#include <bits/stdc++.h> using namespace std; typedef long long int LL; const int INF = (~(1<<31)); const int N = 100000+7; const double eps = 1e-7; inline int read(){ int x=0,f=1;char ch = getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f; } /****************************************************/ struct edge{ int to,next,w; }T[N<<1]; int head[N],tot; int xt[N],mx; int cnt[N<<1]; void add(int u,int v,int w){ T[tot].w=w,T[tot].to=v,T[tot].next=head[u],head[u]=tot++; T[tot].w=w,T[tot].to=u,T[tot].next=head[v],head[v]=tot++; } void dfs(int u,int fa,int xr){ xt[u]=xr,cnt[xr]++; mx=(mx>xr)?mx:xr; for(int i=head[u],to;i!=-1;i=T[i].next){ to=T[i].to; if(to==fa) continue; dfs(to,u,xr^T[i].w); } } int main(){ int _; scanf("%d",&_); while(_--){ mx = tot = 0; memset(cnt,0,sizeof(cnt)); memset(head,-1,sizeof(head)); int n; scanf("%d",&n); for(int i=1,u,v,w;i<n;i++){ scanf("%d%d%d",&u,&v,&w); add(u,v,w); } dfs(1,-1,0); int q,x; scanf("%d",&q); while(q--){ scanf("%d",&x); LL ans = 0ll; for(int i=1;i<=n;i++){ //if((xt[i]^i)>mx) continue; ans+=cnt[x^xt[i]]; } if(!x) ans+=n; ans>>=1; printf("%I64d\n",ans); } } return 0; }