Codeforces Round #835 (Div. 4) G. SlavicG’s Favorite Problem

Let’s ignore the teleporting, and decide how to find the answer. Note that we don’t need to ever go over an edge more than once, since going over an edge twice cancels out (since aaa XOR a=0a=0a=0 for all a). In other words, the only possible value of xxx equals the XOR of the edges on the unique path from aaa to bbb. We can find it through aaa BFS from aaa, continuing to keep track of XOR s as we move to each adjacent node, and XOR ing it by the weight of the corresponding edge as we travel across it.

Now let’s include the teleport. It means that we travel from a→ca→ca→c, then teleport to ddd, and go from d→bd→bd→b, for some nodes ccc and ddd. Also, we cannot pass bbb on the path from a→ca→ca→c.

Again, note that the value of xxx is fixed on each of the paths from a→ca→ca→c and d→bd→bd→b, since there is aaa unique path between them. Let x1x_1x1​ be the XOR of the first path and x2x_2x2​ be the XOR of the second. Then we need x1x_1x1​ XOR x2=0x2=0x2=0 ⟹⟹⟹ x1=x2x_1=x_2x1​=x2​. So we need to find if there are two nodes ccc, ddd such that the XORs from a and b to those nodes are the same. To do this, we can do our BFS from before, but instead run one BFS from a and another from bbb, and check if any two values are the same.

Make sure not to include nodes past bbb while we look for ccc on our BFS from aaa.

The time complexity is O(nlogn)O(nlogn)O(nlogn).

#include
using namespace std;typedef pair PII;int main()
{int T=1;cin>>T;while(T--){int n,a,b;cin>>n>>a>>b;vector> g(n+1);for(int i=1;i<=n-1;i++){int u,v,w;cin>>u>>v>>w;g[u].push_back({v,w});g[v].push_back({u,w});}vector> f(2,vector(n+1));function dfs=[&](int u,int val,int id,int fa){f[id][u]=val;for(auto &[v,p]:g[u]){if(v==fa || v==b) continue;dfs(v,val^p,id,u);}};dfs(a,0,0,-1);dfs(b,0,1,-1);set st;for(int i=1;i<=n;i++)st.insert(f[0][i]);bool ok=false;for(int i=1;i<=n;i++)if(i!=b && st.count(f[1][i]))ok=true;if(ok) cout<<"YES"<