题目链接：点击打开链接
Another Tree Time Limit: 1000 MSMemory Limit: 32768 K Total Submit: 42(16 users)Total Accepted: 15(14 users)Rating: Special Judge: No Description
给出一棵有N个节点(2 <= N <= 500000)和N-1条边的树，每条边拥有一个长度L(1 <= L <= 500000)。
定义：
（1） path(u, v) = 顶点u和v之间的最短路。
（2） xor-distance(u, v) = ⊕e∈path(u,v)length(e),⊕代表异或操作。
请计算出有多少对点的xor-distance的值等于K（0 <= K <= 500000）。（v != u 并且 pair(u,v) = pair(v,u)）。
Input第一行是一个整数T，表示有T组测试数据。
接下来T组测试数据，每组测试数据开始为两个正整数N，K，接下来N-1行每行包含三个整数u,v,L(0 <= u,v <= N-1),代表树中存在一条顶点为u，v，边长为L的边。
Output每组一行，输出点对的个数。
Sample Input2
4 1
0 1 1
1 2 3
2 3 2
3 0
0 1 7
0 2 7
Sample Output
2
1
Source2016级新生程序设计全国邀请赛
题解：就是给你n个数字，问有多少对数字异或后等于k，在树上BFS去找到这些数字，然后统计找到的数字数字和K值出现的次数，将他们加到答案中, 最后除以2就是对数了。
AC代码：
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<queue> #include<map> using namespace std; #define N 500005 struct Node { int to,w; Node(int _to,int _w):to(_to),w(_w){} }; /* struct Node { int to,w; Node(int to,int w) { this->to = to; this->w = w; } }; */ vector<Node> v[N]; queue<int> q; map<int,long long> K_num; int vis[N],dis[N]; void bfs(int s) { while(!q.empty()) q.pop(); q.push(s); vis[s] = 1; dis[s] = 0; while(!q.empty()) { int now = q.front(); //printf("%d\n",now); q.pop(); K_num[dis[now]]++; //printf("tot[%d]=%d\n",dis[now],tot[dis[now]]); int len = v[now].size(); //当前节点now的大小 for(int i = 0; i < len; i++) { int next = v[now][i].to; int next_w = v[now][i].w; //printf("next=%d next_w=%d\n",next,next_w); if(vis[next]==0) { vis[next] = 1; dis[next] = dis[now]^next_w; //printf("dis[%d]=%d\n",next,dis[next]); q.push(next); } } } } int main() { int t,n,k,x,y,w; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&k); for(int i = 0; i < n; i++) v[i].clear(); for(int i = 1; i < n; i++) { scanf("%d%d%d",&x,&y,&w); v[x].push_back(Node(y,w)); v[y].push_back(Node(x,w)); } K_num.clear(); memset(vis,0,sizeof(vis)); // puts("**************"); bfs(0); //puts("**************"); long long ans = 0; for(int i = 0; i < n; i++) { //printf("dis[%d]=%d\n",i,dis[i]); if(k==0) ans += K_num[ k^dis[i] ]/2; else ans += K_num[ k^dis[i] ]; } ans = ans/2; printf("%lld\n",ans); } return 0; } /* 2 4 1 0 1 1 1 2 3 2 3 2 3 0 0 1 7 0 2 7 */ /* 2 1 */
