【树上染色】CF1760G

柔光的暖阳◎ 2024-03-16 11:57 11阅读 0赞

[Problem - G - Codeforces][]

题意：

![19660cc196e8479e96351e9dab4e653f.png][]

思路：

我们需要找到一个点，使得a点到x点的路径异或和=x点到b点的路径异或和，这样总的异或就是0了

所以考虑树上染色，先从a点染异或值，再从b点染

树上染色的颜色一般写在dfs的参数里

Code：

#include <bits./stdc++.h>
    
    using namespace std;
    
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    
    struct ty{
    	int to,next,w;
    }edge[mxe<<1];
    
    map<int,int> mp;
    
    int n,a,b,u,v,w,tot=0,ok=0;
    int head[mxn];
    
    void add(int u,int v,int w){
    	edge[tot].w=w;
    	edge[tot].to=v;
    	edge[tot].next=head[u];
    	head[u]=tot++;
    }
    void dfs1(int u,int fa,int cur){
    	mp[cur]++;
    	for(int i=head[u];~i;i=edge[i].next){
    		if(edge[i].to==fa) continue;
    		if(edge[i].to==b) continue;
    		dfs1(edge[i].to,u,cur^edge[i].w);
    	}
    }
    void dfs2(int u,int fa,int cur){
    	for(int i=head[u];~i;i=edge[i].next){
    		if(edge[i].to==fa) continue;
    		dfs2(edge[i].to,u,cur^edge[i].w);
    		if(ok){
    			return;
    		}
    		if(mp[cur^edge[i].w]){
    			ok=1;
    			cout<<"YES"<<'\n';
    			return;
    		}
    	}
    }
    void G_init(){
    	ok=0;
    	tot=0;
    	for(int i=0;i<=n;i++){
    		head[i]=-1;
    	}
    	mp.clear();
    }
    void solve(){
    	cin>>n>>a>>b;
    	G_init();
    	for(int i=1;i<=n-1;i++){
    		cin>>u>>v>>w;
    		add(u,v,w);
    		add(v,u,w);
    	}
    	dfs1(a,-1,0);
    	ok=0;
    	dfs2(b,-1,0);
    	if(!ok) cout<<"NO"<<'\n';
    }
    int main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int T=1;
    	cin>>T;
    	while(T--)solve();
    	return 0;
    }

[Problem - G - Codeforces]: https://codeforces.com/contest/1760/problem/G
[19660cc196e8479e96351e9dab4e653f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/9ec9e10963994468848d6aab9c279ac1.png