TMTR8-Editorial (2021 HEADLINES)

PROBLEM LINK:

Practice
Contest

Author: Dharsan R
Tester: Dharsan R
Editorialist: Dharsan R

DIFFICULTY:

HARD

PREREQUISITES:

Tree,Union-Find Algorithm,LCA,Square-root decomposition,DFS,XOR

PROBLEM:

Given a tree,a modified tree have to be designed based on the given permutation P if S=1
else if S=0 the given tree is considered as the modified tree.

If S=1, for every valid i,j,k (1 \leq i,j,k \leq N) , if i<j<k then P[i] should be the ancestor of P[j] and P[k], and if P[i] lies in the path between P[j] and P[k] , then P[j] and P[k] belong to two different subtrees of P[i] else they belong to the same subtree.

Once the new tree is designed, find the XOR value of all the nodes except the nodes
that lie in the path of the nodes u and v (inclusive) for each query.

EXPLANATION:

Let’s denote given tree as T1 and the decomposed tree as T2 i,e; the New tree that has to be designed. Construct the new tree, T2 with the help of DSU and the knowledge about T1.

Start from the node on which the operation will be performed on i-th iteration, and construct the tree T2 in the bottom to the top manner (if i<j, then $P[i]$​ will be an ancestor of P[j]). In other words, for i-th iteration from N to 1 (decreasing order), including the P[i] into T2, and add edges from P[i] to those neighbours of P[i] (use T1 to get this information) who have already been included in T2. Simply, in T2, connect P[i] with the root of each component in which P[i]'s neighbour is present.

  • How to decide who will be the root r of the component?
    • The latest added node will always become the root of the component since the operation on this node will affect all its children. This is easy to maintain and process with DSU.

Preprocessing:

Once the new tree is designed, in order to perform the queries efficiently certain preprocessing have to done.

Let u and v be the two nodes upon which the query have to executed, and let us use an array D, where D[i] stores the XOR of the paradox values of all the nodes from node i to the root r. Initialization of the array D can be done in a single DFS traversal. Also let Y be the XOR of all the paradox values of the nodes.

Now for each query u,v the task is to find the XOR of paradox values of all the nodes except that lie in the path between u and v. If X is the paradox values of all the nodes that lie in the path between u and v then X \bigoplus Y gives you the result of the the given query.

Now the task reduces to find X in the most efficient manner. We use the concept of LCA (Lowest Common Ancestor) here.

If w is the LCA of u and v then, D[u] \bigoplus D[v] \bigoplus A[w] = X

Once again the problem reduces to find the LCA of the nodes efficiently. This can be done be using Square root decomposition method.

Subtask1:

Can be solved by Naive Algorithm without any tree updation .

Subtask2:

Can be solved using LCA by Square root decomposition method without any tree updation .

Subtask3:

Can be solved by direct LCA method with tree updation .

Subtask4:

Can only be solved by using Square root decomposition with tree updation .

TIME COMPLEXITY:

O(Q*Sqrt(H)+N) where Q is the number of queries, N is the number of nodes and
H is the height of the tree.

SOLUTIONS:

Setter's Solution
#include<iostream>
#include<bits/stdc++.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<cstdio>
using namespace std;
int child[100005],vis[100005];
long p[100005],parent[100005],depth[100005],jump[100005];
long long a[100005],s[100005];
vector<long> e[100005],tree[100005];
void init()
{
	for(int i=0;i<100005;i++)
	{
		e[i].clear();
		tree[i].clear();
	}

}
long find(long i)
{
    if(parent[i]==i)
    {
        return i;
    }
    else
    {
        long node=find(parent[i]);
        parent[i]=node;
        return node;
    }
}
void join(long u,long v)
{
    long node1=u;
    long node2=find(v);
    tree[node1].push_back(node2);
    tree[node2].push_back(node1);
    parent[node2]=node1;
    return ;
}
long height(long node,long long k)
{
	k=(k^a[node]);
    s[node]=k;
	vis[node]=1;
	long m=0;
	for(long i=0;i<tree[node].size();i++)
		if(vis[tree[node][i]]==0)
		{
			m=max(m,height(tree[node][i],k));
		}
	return m+1;
}
void dfs(long des,long anc,long d,long root)
{
	if(des!=root)
	{
		depth[des]=depth[anc]+1;
		parent[des]=anc;
		if(depth[des]%d==0)
			jump[des]=parent[des];
		else
			jump[des]=jump[anc];
	}
    for(long i=0;i<tree[des].size();i++)
        if(tree[des][i]!=anc)
            dfs(tree[des][i],des,d,root);
}
long naive(long u,long v)
{
    if(u==v)  
		return u;
    if(depth[u]>depth[v])
        swap(u,v);
    v=parent[v];
    return naive(u,v);
}
long lca(long u,long v)
{
    while(jump[u]!=jump[v])
    {
        if(depth[u]>depth[v])
            swap(u,v);
        v=jump[v];
    }
    return naive(u,v);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t;
	long n,x,y,k,q,root,m,u,v,d;
	cin>>t;
	while(t--)
	{
	    cin>>n>>q;
	    for(long i=0;i<n;i++)
	    {
	        child[i]=0;
	        vis[i]=0;
	        parent[i]=i;
	    }
	    long long X=0;
	    for(long i=0;i<n;i++)
	    {
	        cin>>a[i];
	        s[i]=0;
	        X=(X^a[i]);
	    }
	    for(long i=0;i<n-1;i++)
	    {
	        cin>>x>>y;
	        e[x-1].push_back(y-1);
	        e[y-1].push_back(x-1);
	    }
		int choice;
		cin>>choice;
		if(choice==1)
		{
			for(int i=0;i<n;i++)
				cin>>p[i];
			for(long i=n-1;i>=0;i--)
			{
				k=p[i]-1;
				for(long j=0;j<e[k].size();j++)
				{
					if(child[e[k][j]]==1)
					{
						join(k,e[k][j]);
					}
				}
				child[k]=1;
			}
			root=p[0]-1;
		}
		else
		{
			for(int i=0;i<100005;i++)
				tree[i]=e[i];
			root=0;
		}
		m=height(root,0);
		d=sqrt(m);
		for(long i=0;i<n;i++)
			vis[i]=0;
		depth[root]=0;
	    dfs(root,0,d,root);
	    while(q--)
	    {
	        cin>>u>>v;
	        u--;
	        v--;
	        long node=lca(u,v);
	        long long ans=(s[u]^s[v]);
	        ans=(ans^a[node]);
	        ans=(ans^X);
	        cout<<ans<<"\n";
	    }
		init();
	}
	return 0;
}

1 Like