Problem - G - Codeforces

题意：

思路：

我们需要找到一个点，使得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;
}