# WA in Nutella Path (Euler Tour: help needed)

We need to find xor along the path of two given vertices u and v and answer these queries. My approach: For each vertex store the xor of path from this vertex to the root (in array x[]). Next find the lca of given 2 vertices u and v. Then answer for this query should be:
XORpath(u,v) = x[u]^x[v]^(value of vertex in lca vertex)

The editorial uses binary lifting to find LCA. I have used Euler Tour traversal of tree approach instead, which reduces problem to RMQ (reference: cp-algs). Have used segment tree for RMQ, that that stores pair of height of vertex in euler tour and the vertex in euler tour. Answer is query.second .

I tried debugging my Euler tour array as well as my segment tree but it seems they are working fine. My code passes for sample test cases, and many of my own custom cases. Why is my code getting a WA?

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int const siz=1e5;
int depth[siz+1], euler[2*siz], first[siz+1], x[siz+1],n;
bool vis[siz+1];
pair<int,int> t[4*siz+1];

void dfs(int &idx,int d,int v,int parent) {
vis[v]=true;
depth[v]=d;
euler[idx]=v;
first[v]=idx;
idx++;
x[v]^=x[parent];
for (auto i:adj[v]) {
if (!vis[i]) {
dfs(idx,d+1,i,v);
euler[idx++]=v;
}
}
}

void build(int v,int tl,int tr) {
if (tl==tr) {
t[v]=make_pair(depth[euler[tl]],euler[tl]);
return;
}
int mid=(tl+tr)/2;
build(2*v,tl,mid);
build(2*v+1,mid+1,tr);
t[v]=min(t[2*v],t[2*v+1]);
}

pair<int,int> qry(int v,int tl,int tr,int l,int r) {
if (l>r)
return make_pair(100001,100001);
if (l==tl && r==tr)
return t[v];
int mid=(tl+tr)/2;
return min(qry(2*v,tl,mid,l,min(r,mid)),qry(2*v+1,mid+1,tr,max(l,mid+1),r));
}

int LCA(int u,int v) {
return qry(1,1,2*n-1,u,v).second;
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T; cin>>T;
while (T--) {
int q; cin>>n>>q;
int arr[n+1];
for (int i=1;i<=n;i++) {
vis[i]=false;
cin>>x[i];
arr[i]=x[i];
}
for (int i=1;i<n;i++) {
int u,v; cin>>u>>v;
}
int idx=1;
dfs(idx,0,1,0);
build(1,1,2*n-1);
while (q--) {
int u,v; cin>>u>>v;
int left=first[u];
int right=first[v];
if (left>right) swap(left,right);
int a=arr[LCA(left,right)]^x[u]^x[v];
cout<<a<<"\n";
}
}
return 0;
}

My guess is that x is never initialized, so in dfs when you set x[v]^=x[parent], for v = 1, parent is 0, and x[0] could be some garbage value.

Tell me if it still doesn’t work after fixing that.

Since x[] is a global array, x[0] must be 0 instead of garbage value, so for x[0]=0 we should get x[1] as the the value of vertex itself. I added x[0]=0 in my code in the test case loop but still got a WA…

Huh, sorry, didn’t know that about global arrays.

Maybe your segment tree is wrong? I’ve never seen a condition like if (l==tl && r==tr) before, the typical thing to do would be to check if the tree’s interval is fully inside or outside the query’s interval.

Also, I’m not giving up, but it’s generally a good idea to learn the binary lifting version (it has more applications), and I’ve never had a situation where euler tour was necessary over binary lifting.

I have used the implementation of my segment tree as in here: https://cp-algorithms.com/data_structures/segment_tree.html under the implementation header. (l==tl && r==tr) checks if the segment overlaps or not, then we accordingly go left or right. I tried debugging my segment tree quite many times but it seems to work well…
Why prefer binary lift over euler tour, is it easier to code or other reasons?

So I copied your exact code but modified it to instead use my (working) LCA template, and it was accepted. I am currently trying to figure out why.

I guess cp-algorithms is right (unless it isn’t), I didn’t consider how the min and max would change stuff.

Binary lifting has more uses so it’s more useful to understand (such as static O(\log{n}) path RMQ). Ideally, it being easy to code shouldn’t matter as you can mostly template everything, but yes, I find it easier to implement than a segment tree.

If it worked with your template, the problem must be with the segment tree itself I guess… found no luck yet though figuring out WA for this. And sure I’ll look into binary lifting more

@galencolin Any luck yet? Also do you think it’d be appropriate to seek out help on stackoverflow for questions like these?

Finally figured out the problem!
At line number 9, the size of the segment tree should be 4*(2siz-1)+1 not 4siz+1, since euler tour visits 2*n-1 nodes. Codechef judge should have given me RE instead of a WA, don’t know why it doesn’t. Would have saved hours.