ENOC1 - Editorial

editorial
, , , ,
1

Practice : Click here
Contest : Click here

Author : Soham Chakrabarti
Tester : Arkapravo Ghosh
Editorialist : Soham Chakrabarti

Difficulty :

Easy - Medium

PREREQUISITES:

Lowest Common Ancenstor, Dp on trees

PROBLEM:

Given a tree with N nodes and N−1 edges and Q queries, find the XOR of the shortest path from node u to v.

EXPLANATION:

Having knowledge of LCA is essential. Click to read more about lowest common ancestor of two nodes.

Coming to the problem, we have to store the XOR of nodes in a DP table as there is going to be queries ( Q \le 10^5 ).
We are going to build the DP table using Binary Lifting of Nodes.

Build DP table

void dfs(int u, int par, int v = -1, int h=0)
{
lvl[u] = h;
up[u][0] = par;
if(v!=-1)dp[u][0]=v;
FR(i,1,LG+1)
{
up[u][i] = up[up[u][i-1]][i-1];
dp[u][i] = (dp[u][i-1] ^ dp[up[u][i-1]][i-1]);
}
for(auto x:G[u])
{
if(x != par) dfs(x, u, val[x], h+1);
}
}

After successfully building the DP table storing XOR, we take every query containing the two nodes u and v and get the LCA of the two nodes.

Let us take x = lca(u,v),

By taking data from the DP table, we go from node to node ( u to x ) and ( v to x ) and keep XOR-ing the result. (considering some cases)

LINKS:

Author’s Solution : Click here

Tester’s Solution : Click here

2 Likes
2

I used Euler Tour to find the lca (used segment trees for RMQ, the segment tree stores the pair of depth of vertex and the vertex).
Xor along path= (xor from u to lca)^(xor from lca to v)^arr[lca] (used this, where arr[lca] is the value of lca’s vertex)
My code is getting a WA. My code passes for sample test cases and I tried many of my own test cases too. Please help me figuring out what am I doing wrong:

#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;
}
3

I made a simple dp table. dp[i] denotes the xor of all values on the path from node i to root node.
For each query , let x = lca(u,v), then
answer = dp[u]^dp[v]^value[x]

1 Like
4

@arjunbangari Can u share ur code…since DSA contest is ongoing , unable to view ur solution.

5

Here -CodeChef: Practical coding for everyone

6 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;

int xortable[100005];
vector<vii> tree;
int a[100005];
int dp[100005][20];
int n;
int depth[10005];

void dfs(int idx,int p){
    dp[idx][0] = p;
    depth[idx] = depth[p]+1;
    for(int i=0;i<log2(n);i++){
        dp[idx][i] = dp[dp[idx][i-1]][i-1];
    }
    for(int j=0;j<tree[idx].size();j++){
        ii v = tree[idx][j];
        if(v.first!= p){
            xortable[v.first] = xortable[idx]^a[v.first];
            dfs(v.first,idx);
        }
    }
}

int lca(int u,int v){
    if(depth[u] < depth[v]) swap(u,v);
    int diff = depth[u] - depth[v];
    for(int i=0;i<log2(n);i++){
        if((1<<i) & diff) u = dp[u][i];
    }
    if(u==v) return u;
    for(int i=log2(n)-1;i>=0; i--){
        if(dp[u][i] != dp[v][i]){
            u = dp[u][i];
            v = dp[v][i];
        }
    }
    return dp[u][0];
}

main(){
    int t;cin>>t;
    while(t--){
        int q;
        cin>>n>>q;
        tree.assign(n+1,vii());
        memset(dp,0,sizeof(dp));
        cin>>a[1];
        xortable[1] = a[1];
        for(int i=2;i<=n;i++) cin>>a[i];
        int edges = n-1;
        int x,y;
        while(edges--){
            cin>>x>>y;
            tree[x].push_back(ii(y,1));
            tree[y].push_back(ii(x,1));
        }
        dfs(1,1);
        while(q--){
            cin>>x>>y;
            int lcavalue = lca(x,y);
            ll ans = xortable[x]^xortable[y]^a[lcavalue];
            cout<<ans<<"\n";
        }
    }
}

Can u check what’s the mistake in my code?@arjunbangari

7

if(dp[u][i] != dp[v][i]){. --> instead use this condition if( LCA[a1][i]!=-1 && (LCA[a1][i]!=LCA[b][i]))

8

dp value is never -1.Should I change to dp[u][i]!= 0;
Also can u explain y the change is required.

11

the change is required since 1st if condition deals whens 2^n th parent is avaliable and the second condition when both don’t have same parent

12

yes that would be better

13

Can someone tell me why does this TLE in java? Seem to have done exactly what’s told in editorial?

14 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define int long long int
#define double long double
#define inf (int)(1e15)
#define all(x) (x).begin(), (x).end()
#define pair pair<int, int>
typedef vector<int> vi;   // Vector of long long
typedef vector<vi> vvi;   // Vector of vi
typedef vector<pair> vii; // Vector of pairs
typedef vector<vii> vvii; // Vector of Vector of pairs
typedef vector<bool> vb;  // Vector of bool
#define pq priority_queue // Max heap (To convert to min heap, use negative sign before every value)
#define ff first          // For pairs
#define ss second
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, -1, 0, 1};
const int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1}, dy8[] = {1, -1, 1, 0, -1, 1, -0, -1};
#define testcases(t) \
    int(t);          \
    cin >> (t);      \
    while ((t)--)
vi depth, a;
vvi adj;
vvii dp;
int n, u, v, ans = 0;
vb visited;
int walk(int i, int k)
{
    int bit = 0;
    while (k > 0)
    {
        if (k & 1)
        {
            ans ^= dp[bit][i].second;
            i = dp[bit][i].first;
        }
        bit++;
        k >>= 1;
    }
    return i;
}
int solve(int i, int j)
{
    ans = 0;
    if (depth[i] > depth[j])
        i = walk(i, depth[i] - depth[j]);
    if (depth[j] > depth[i])
        j = walk(j, depth[j] - depth[i]);
    if (i == j)
        return ans ^ a[i];
    for (int k = log2(n); k >= 0; k--)
    {
        if (dp[k][i].first != dp[k][j].first)
        {
            ans ^= dp[k][i].second;
            ans ^= dp[k][j].second;
            i = dp[k][i].first;
            j = dp[k][j].second;
        }
    }
    ans = ans ^ a[i] ^ a[j] ^ a[dp[0][i].first];
    return ans;
}
signed main()
{
    testcases(t)
    {
        int n, queries;
        cin >> n >> queries;
        adj.resize(n + 1);
        visited.resize(n + 1, false);
        depth.resize(n + 1, 0);
        a.resize(n + 1);
        dp.resize(log2(n) + 1);
        for (int i = 0; i <= (log2(n)); i++)
        {
            dp[i].resize(n + 1);
        }
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
        }
        for (int i = 1; i < n; i++)
        {
            cin >> u >> v;
            adj[u].pb(v);
            adj[v].pb(u);
        }
        queue<int> q;
        q.push(1);
        visited[1] = true;
        depth[1] = 0;
        while (q.size())
        {
            int node = q.front();
            q.pop();
            for (auto it : adj[node])
            {
                if (visited[it])
                    continue;
                visited[it] = true;
                depth[it] = depth[node] + 1;
                dp[0][it].first = node;
                dp[0][it].second = a[it];
                q.push(it);
            }
        }
        for (int k = 1; k <= (log2(n)); k++)
        {
            for (int i = 1; i <= n; i++)
            {
                if (i == 1)
                    dp[k][i].first = 1, dp[k][i].second = a[1];
                else
                {
                    dp[k][i].first = dp[k - 1][dp[k - 1][i].first].first;
                    dp[k][i].second = dp[k - 1][i].second ^ dp[k - 1][dp[k - 1][i].first].second;
                    // cout << k << " " << i << endl;
                }
            }
        }
        while (queries--)
        {
            cin >> u >> v;
            cout << solve(u, v) << endl;
        }
    }
    return 0;
}

Whats wrong with my code. I keep getting wrong answer