16哈理工新生赛 J Another Tree （树上BFS）

淡淡的烟草味﹌ 2022-07-14 11:39 59阅读 0赞

题目链接：[点击打开链接][Link 1]

<table> 
 <tbody> 
 <tr> 
 <td>Another Tree</td> 
 </tr> 
 <tr> 
 <td> 
 <table> 
 <tbody> 
 <tr> 
 <td>Time Limit: 1000 MS</td> 
 <td>Memory Limit: 32768 K</td> 
 </tr> 
 </tbody> 
 </table> 
 <table> 
 <tbody> 
 <tr> 
 <td>Total Submit: 42(16 users)</td> 
 <td>Total Accepted: 15(14 users)</td> 
 <td>Rating: <img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-half2.png" alt=""></td> 
 <td>Special Judge: No</td> 
 </tr> 
 </tbody> 
 </table> </td> 
 </tr> 
 <tr> 
 <td>Description</td> 
 </tr> 
 <tr> 
 <td> 给出一棵有N个节点(2 &lt;= N &lt;= 500000)和N-1条边的树，每条边拥有一个长度L(1 &lt;= L &lt;= 500000)。 定义： （1）&nbsp;&nbsp;path(u, v) = 顶点u和v之间的最短路。 （2）&nbsp;&nbsp;xor-distance(u, v) = ⊕e∈path(u,v)length(e),⊕代表异或操作。 请计算出有多少对点的xor-distance的值等于K（0 &lt;= K &lt;= 500000）。（v != u 并且 pair(u,v) = pair(v,u)）。 </td> 
 </tr> 
 <tr> 
 <td>Input</td> 
 </tr> 
 <tr> 
 <td> 第一行是一个整数T，表示有T组测试数据。 接下来T组测试数据，每组测试数据开始为两个正整数N，K，接下来N-1行每行包含三个整数u,v,L(0 &lt;= u,v &lt;= N-1),代表树中存在一条顶点为u，v，边长为L的边。 </td> 
 </tr> 
 <tr> 
 <td>Output</td> 
 </tr> 
 <tr> 
 <td> 每组一行，输出点对的个数。 </td> 
 </tr> 
 <tr> 
 <td>Sample Input</td> 
 </tr> 
 <tr> 
 <td> 2 4&nbsp;1 0&nbsp;1&nbsp;1 1&nbsp;2&nbsp;3 2&nbsp;3&nbsp;2 3&nbsp;0 0&nbsp;1&nbsp;7 0&nbsp;2&nbsp;7 </td> 
 </tr> 
 <tr> 
 <td>Sample Output</td> 
 </tr> 
 <tr> 
 <td> 2 1 </td> 
 </tr> 
 <tr> 
 <td>Source</td> 
 </tr> 
 <tr> 
 <td>2016级新生程序设计全国邀请赛</td> 
 </tr> 
 </tbody> 
</table>

题解：就是给你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
 */

[Link 1]: http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=2302