G. SlavicG‘s Favorite Problem(树的遍历DFS,BFS均可)

Problem - G - Codeforces

给你一棵有n个顶点的加权树。回顾一下，树是一个没有任何循环的连接图。加权树是一棵树，其中每条边都有一定的权重。这棵树是无定向的，它没有根。

由于树让你感到厌烦，你决定挑战自己，在给定的树上玩一个游戏。

在一次移动中，你可以从一个节点移动到它的一个邻居（与它有直接边的另一个节点）。

当你通过边i时，x的值变为x XOR wi（其中wi是第i条边的权重）。

你的任务是从顶点a到顶点b，但你被允许进入节点b，当且仅当旅行到它之后，x的值将变成0。换句话说，你只能通过使用边i，使x XOR wi=0来旅行到节点b。

此外，你可以在任何时间点最多传送一次到任何顶点，除了顶点b。你可以从任何顶点传送，甚至从a点传送。

如果你能从a到达顶点b，则回答 "是"，否则回答 "否"。

请注意，XOR代表位XOR操作。

输入
第一行包含一个整数t（1≤t≤1000）--测试案例的数量。

每个测试案例的第一行包含三个整数n、a和b（2≤n≤105），（1≤a,b≤n;a≠b）--分别是顶点的数量，以及起始节点和期望的结束节点。

接下来的n-1行中的每一行表示树的一条边。边缘i由三个整数ui、vi和wi表示--它连接的顶点的标签（1≤ui,vi≤n;ui≠vi;1≤wi≤109）和各自边缘的权重。

保证所有测试案例的n之和不超过105。

输出
对于每个测试案例，如果你能到达顶点b，则输出 "YES"，否则输出 "NO"。

例子
输入复制
3
5 1 4
1 3 1
2 3 2
4 3 3
3 5 1
2 1 2
1 2 2
6 2 3
1 2 1
2 3 1
3 4 1
4 5 3
5 6 5
outputCopy
是
没有
是
注意
对于第一个测试案例，我们可以从节点1到节点3，x从0变成1，然后我们从节点3到节点2，x变成等于3。现在，我们可以传送到节点3，从节点3到节点4，到达节点b，因为x最后变成等于0，所以我们应该回答 "是"。

对于第二个测试案例，我们没有移动，因为我们不能传送到节点b，我们唯一的移动是前往节点2，这是不可能的，因为到达节点2时x不会等于0，所以我们应该回答 "不"。

题解:
我们必须搞清楚一点当你旅行到b后,x的值是必须为0的,也就是说走到b后就要停下了(很重要)

a可以通过传送达到除b外的任意一点,并且每经过一条路径就要做^操作,

我们不妨双向考虑,从起点与终点出发,如果a遍历到某一点的值,与b遍历到某一点的值相等,那么是不是可以让a直接传送到b遍历到的点,众所周知,两个相等的值^结果为0,最终到达b点的值也会为0

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<queue>
using namespace std;
vector<pair<int,int>> p[100050];
int n,a,b;
int f = 0;
int dis[100050];
int vis[100050];
int dis1[100050];
int vis1[100050];
map<int,int> rr,ll;
void bfs()
{
	queue<int> q;
	q.push(a);
	dis[a] = 0;
	while(q.size())
	{
		auto ver = q.front();
		q.pop();
		if(vis[ver])
		continue;
		vis[ver] = 1;
		for(int i = 0;i < p[ver].size();i++)
		{
			auto j = p[ver][i];
			int ne = j.first;
			int ww = j.second;
			if(!vis[ne])
			{
				if(ne != b)
				{
				dis[ne] = ww^dis[ver];
				q.push(ne);
				}
			}
		}
	}
}
 
void bfs1()
{
	queue<int> q;
	q.push(b);
	dis1[b] = 0;
	while(q.size())
	{
		auto ver = q.front();
		q.pop();
		if(vis1[ver])
		continue;
		vis1[ver] = 1;
		for(int i = 0;i < p[ver].size();i++)
		{
			auto j = p[ver][i];
			int ne = j.first;
			int ww = j.second;
			if(!vis1[ne])
			{
				dis1[ne] = ww^dis1[ver];
				rr[dis1[ne]] = 1;
				q.push(ne);
			}
		}
	}
}
void solve()
{
	f = 0;
	cin >> n >> a >>b;
	rr.clear();
	ll.clear();
	for(int i = 1;i <= n;i++)
	{
		p[i].clear();
		vis[i] = 0;
		dis[i] = 0;
		vis1[i] = 0;
		dis1[i] = 0;
	}
	for(int i = 1;i < n;i++)
	{
		int l,r,w;
		cin >> l>>r>>w;
		p[l].push_back({r,w});
		p[r].push_back({l,w});
	}
	bfs();
	bfs1();
	for(int i = 1;i <= n;i++)
	{
		if(rr[dis[i]])
		{
			cout<<"YES\n";
			return ;
		}
	}
	cout<<"NO\n";
}
signed main()
{
	int t = 1;
	cin >> t;
	while(t--)
	{
		solve();
	}
}