Problem: https://www.codechef.com/problems/ENOC1
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;
vector<int> adj[siz+1];
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;
adj[i].clear();
cin>>x[i];
arr[i]=x[i];
}
for (int i=1;i<n;i++) {
int u,v; cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
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;
}