Lowest Common Ancestor |
All submissions for this problem are available.
Read problems statements in
In a rooted tree, the lowest common ancestor (or LCA for short) of two vertices u and v is defined as the lowest vertex that is ancestor of both that two vertices.
Given a tree of N vertices, you need to answer the question of the form "r u v" which means if the root of the tree is at r then what is LCA of u and v.
Input
The first line contains a single integer N. Each line in the next N - 1 lines contains a pair of integer u and vrepresenting a edge between this two vertices.
The next line contains a single integer Q which is the number of the queries. Each line in the next Q lines contains three integers r, u, v representing a query.
Output
For each query, write out the answer on a single line.
Constraints
20 points:
- 1 ≤ N, Q ≤ 100
40 points:
- 1 ≤ N, Q ≤ 105
- There is less than 10 unique value of r in all queries
40 points:
- 1 ≤ N, Q ≤ 2 × 105
Example
Input: 4 1 2 2 3 1 4 2 1 4 2 2 4 2 Output: 1 2
Explanation
- "1 4 2": if 1 is the root, it is parent of both 2 and 4 so LCA of 2 and 4 is 1.
- "2 4 2": the root of the tree is at 2, according to the definition, LCA of any vertex with 2 is 2.
-------------------------------------------------------------------EDITORIAL--------------------------------------------------------------------------
THERE ARE FEW OBSERVATIONS TO SOLVE THIS PROBLEM
OBSERVATION 1 ->
IF THE LEVEL OF NEW ROOT IS LESS THAN THE LEVEL OF THE LCA OF A AND B THAN LCA OF A ,B REMAIN SAME
OBSERVATION 2 ->
IF THE NODE C IS NOT IN THE SUB TREE OF THE LCA OF A AND C THAN ALSO LCA OF A AND B REMAIN SAME ,, THIS CAN BE CHECK USING START TIME AND END TIME
OBSERVATION 3 ->
ELSE ANS WILL BE THE NODE WHICH IS THE DEEPEST NODE AMONG (LCA(A,C) , LCA(B,C))
------------------------------------------------CHEF EDITORIAL-----------------------------------------------------------------------------------------
Problem : Given a tree, you have to answer the question of the format "r u v" which means which is the LCA of u and v if the root of the tree is at r.
Explanation
At first, let's consider some partial solutions.
How to get 20 points
For this sub-task you an find the LCA in any way you want as long as the complexity is not slower than O(N). For example, by DFS from the root, you can number the vertices so that given two arbitrary vertices, you can check whether they are ancestor and descendant(for this, you can store T_in and T_out for each node. T_in is the time when the DFS for that node was begun. T_out is the time when the DFS was over).
How to get 60 points
Here there are not more than 10 different roots, but the queries are quite high, so you should know the fast way to find LCA. More specifically O(Nlog(N)) is enough. Notice that there will be no more than 10 different roots so your complexity will be O(10 × Nlog(N)).
How to get 100 points
There are two interesting observations that you can make:
- Given the query "r u v" what can be the answer? The possible answers are r, u, v, LCA(r, u), LCA(r, v), LCA(u, v)where LCA(x, y) is LCA of x and y when the tree is rooted at 1.
- The LCA of u and v when the root is at r is the vertex x such that the sum of shortest path from x to u, x to v and x to r is smallest.
With this two observations you need to implement two function: finding LCA and distance of the two vertices in the tree. Proof for these two observation is not hard but too long to be mentioned here. It is left as an exercise for you.
------------------------------------------------------------------CODE------------------------------------------------------------------------------
// tree is treated as 1 based
// level is also 1 based
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
list<pair<int,int> >li[200010];
lli dp[200010][31];
int lev[200010];
int dist[200010];
int st[200010];
int en[200010];
int timee;
int dfs(int start,int par,int le,int di)
{
st[start]=timee;
lev[start]=le;
list<pair<int,int > >:: iterator it;
for(it=li[start].begin();it!=li[start].end();it++)
{
if(it->first!=par)
{
timee++;
dp[it->first][0]=start;
lev[it->first]=le+1;
dist[it->first]=di+it->second;
dfs(it->first,start,le+1,di+it->second);
}
}
en[start]=timee;
}
int binary_rais(int a,int b)// return lca of a,b
{
if(lev[a]<lev[b]) swap(a,b);
int lg;
/// maximum jump that can be alloweable to make both a and
// b at same level will be the depth of the node a
for(lg=1;(1<<lg)<=lev[a];lg++);
//
lg--;
// this will make both at same level
// we can write any number as the power of 2
// so by binary raise we can reach to any node
for(int i=lg;i>=0;i--)
{
if(lev[a]-(1<<i)>=lev[b])
{
a=dp[a][i];// moving a upward
}
}
// now a and b are at same level
// cout<<" at same level "<<a<<" "<<b<<endl;
if(a==b) return a;
else
{
for(int i=lg;i>=0;i--)
{
if(dp[a][i]!=-1 && dp[a][i]!=dp[b][i])// moving botha and b up
{
a=dp[a][i];
b=dp[b][i];
}
}
return dp[a][0];
}
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n-1;i++)
{
int a,b,c;
cin>>a>>b;
li[a].push_back(make_pair(b,1));
li[b].push_back(make_pair(a,1));
}
memset(dp,-1,sizeof dp);
dist[1]=0;
dp[1][0]=0;
dfs(1,-1,1,0);
int max_h=30;
for(int i=1;i<=max_h;i++)
{
for(int j=1;j<=n;j++)
{
if(dp[j][i-1]!=-1)
dp[j][i]=dp[dp[j][i-1]][i-1];//
}
}
int q;
cin>>q;
while(q--)
{
int a,b,c;
// CASE 1 IF C LIES IN THE PATH OF A AND B THAN C WILL BE THE ANSWER
cin>>a>>b>>c;
int par= binary_rais(a,b);
int ab=dist[a]+dist[b]-2*dist[par];
int ac=dist[a]+dist[c]-2*dist[binary_rais(a,c)];
int bc=dist[b]+dist[c]-2*dist[binary_rais(b,c)];
if(ab==ac+bc)// CONDITION FOR WHICH C LIES IN THE PATH B/W A AND B
{
cout<<c<<endl;
}
else if(lev[c]<=lev[par])// IF THE LEVEL OF C IS LOW THAT C THAN TEHRE
// THERE WILL BE NO CHANGE IN THE LCA
{
cout<<par<<endl;
}
else
{
// CASE 1
// IF THE NODE WHICH WE ARE MAKIHNG THE ROOT
// HAVE LEVEL LESS THAN THE LCA OF A AND B
// AND THIS NODE IS ALSO IN THE SUB TREE
// OF THE LCA OF A AND B
// THAN ANS WILL BE THE
// NODE WHICH HAVE MAXIMUM LEVEL
// AMONG LCA OF A ,C OR LCA OF B,C
int stt=st[par];
int enn=en[par];
if(st[c]>=stt && en[c]<=enn)
{
int lc1= binary_rais(a,c);
int lc2= binary_rais(b,c);
if(lev[lc1]>=lev[lc2])
{
cout<<lc1<<endl;
}
else cout<<lc2<<endl;
}
// CASE 2 LCA REMAIN SAME
else cout<<par<<endl;
}
}
}
No comments:
Post a Comment