Tutorial for Codechef's TREEEDGE (LCA using binary lifting)

Правка en11, от Mooncrater, 2020-02-02 13:14:35

Hello all,

I was trying to learn about binary lifting, and came across this codechef question.

Gist of the question:

You're given a weighted tree. You are given $$$q$$$ operations, which are of the format $$$u,v,x$$$, where $$$u,v$$$ are the nodes of the tree, for which we have to find the maximum weight path which joins them. $$$u,v$$$ are never each other's ancestors. An edge of weight $$$x$$$ can be used to connect the subtrees of $$$u$$$ and $$$v$$$.

Gist of my solution

Case 1: Do not use $$$x$$$ :

If we do not connect $$$u$$$ and $$$v$$$'s subtrees, then we'll have to find their LCA, and the answer would be $$$dist(u,lca)+dist(v,lca)$$$. LCA can be found using binary lifting. The recurrence for binary lifting is:

$$$dp[node][parent] = dp[dp[node][parent-1]][parent-1]$$$

And the distance recurrence is:

$$$distance[node][parent] = distance[node][parent-1]+distance[dp[node][parent-1]][parent-1]$$$

These can be built in the same for loop as done by me in the code.

Case 2: Use $$$x$$$ :

If we use $$$x$$$ and connect the subtrees of $$$u$$$ and $$$v$$$, then we'll do that by connecting the nodes (in the respective subtrees) which are at the maximum distance from $$$u$$$ (in it's subtree) and $$$v$$$(in it's subtree). That is, let's say $$$u_{alpha}$$$ is the node in $$$u$$$'s subtree that is farthest from $$$u$$$, and $$$v_{\alpha}$$$ is the node in $$$v$$$'s subtree that is farthest from $$$v$$$. Then in this case we get a total distance of $$$dist(u,u_{\alpha})+dist(v,v_{\alpha})+x$$$.

We find the maximum of both of these cases, and return the answer.

Cool. Cool theory. Doesn't work.

Explanation for the code:

Variables:

  • depth: Saves the depth of a node from the root

  • mcd: Saves the distance of the maximum distant node in the subtree for the i'th node. Could be zero, if all the members of the subtree are at a negative distance.

  • dp[i][j][0]: Saves the $$$2^j$$$th parent of $$$i$$$

  • dp[i][j][1]: Saves the distance of the $$$2^j$$$th parent of $$$i$$$ from $$$i$$$.

  • vector<pii> al[MAXN]: The adjacency list representation of the tree.

Methods: - dfs1: As named, does a $$$DFS$$$. AIM: To create dp[i][0][0], dp[i][0][1], mcd, and depth. The logic behind calculating the mcd is that you get the distance for each child of a the node, and we add the edge weight and compare it to the current mcd value. So yeah you might have got the point.

  • main: Creation of dp, running dfs1, running a loop for each query et cetera. In the loop, we get the answer for the case 2, int maxD initially. Then we calculate the answer for the case 1. If the two nodes are not at the same level, then we can we bring them on the same level. Let's assume they have a difference of diff in between their levels, then we can jump up this diff. That is a $$$O(log N)$$$ operation in my opinion.( Not opinion, I know but humble++). This can be done by:

  • Move MSB to LSB. That is, if diff=14=(1110), then we go to 2^3rd parent, then from there, go to 2^2nd parent, then from there 2^1st parent, and voila, we're at our destination.

Now, what both our nodes are at the same level, so we go up starting from the 2^19th parent, and go on to j>=0, in order to find the highest ancestors that do not match. In the end, we reach at a point, that is just below the LCA. That is, the parent of u and v is the LCA. Meanwhile, we're also updating our dist variable so store the information of the distance we traverse.

In the end, we compare the values of maxD and dist. Whichever is the greater, is output as the answer.

Here is my code:


#include<iostream> #include<algorithm> #include<vector> #include<cstring> #include<math.h> using namespace std ; #define f(i,s,n) for(int i=s;i<n;i++) #define X first #define Y second #define MAXN 300005 typedef long long ll ; #define pii pair<ll,ll> ll depth[MAXN], mcd[MAXN]; ll dp[MAXN][20][2] ; vector<pii> al[MAXN] ; ll dfs1(int node,int par) {// to create the depth and mcd arrays ll mcdV = 0 ; for(auto x:al[node]) if(x.X!=par) { dp[x.X][0][0] = node ; dp[x.X][0][1] = x.Y ; depth[x.X] = depth[node]+1 ; mcdV = max(mcdV,max(x.Y,x.Y+dfs1(x.X,node))) ; } return mcd[node] = mcdV ; } int main() { ios::sync_with_stdio(0) ; cin.tie(0) ; int T;cin>>T; while(T--) { int n,q ;cin>>n>>q; f(i,0,n+1) al[i].clear() ; f(i,0,n-1) { int u,v,w; cin>>u>>v>>w ; al[u].emplace_back(v,w) ; al[v].emplace_back(u,w) ; } memset(dp,-1,sizeof(dp)) ; memset(depth,0,sizeof(depth)) ; memset(mcd,0,sizeof(mcd)) ; dp[1][0][0] = 0 ;//parent of node 1 is 0 dp[1][0][1] = -1e18 ;//distance of 1's parent from it is very loooww // depth[0] = -1 ; depth[1] = 0 ; dfs1(1,0) ;//dp[i][0][0], depth, mcd filled up now. f(j,1,20) f(i,1,n+1) dp[i][j][0] = dp[dp[i][j-1][0]][j-1][0], dp[i][j][1] = dp[i][j-1][1]+dp[dp[i][j-1][0]][j-1][1] ; //dp created for binary lifting. f(i,0,q) { int u,v,x ;cin>>u>>v>>x ; ll maxD = mcd[u]+x+mcd[v] ; //check if the path to lca is greater than this. if(depth[u]>depth[v]) swap(u,v) ;// u should always be at the lower depth int diff = depth[v]-depth[u] ; long long dist = 0 ; while(diff)//log(3e5)~20 { int jumpto = floor(log2(diff)) ; dist+=dp[v][jumpto][1] ;//<----this way of keeping distances might be wrong v = dp[v][jumpto][0] ; diff -= (1<<jumpto) ; } /* while(diff) { int jumpto = diff&(-diff) ; v = dp[v][(int)log2(jumpto)][0] ; dist+=dp[v][(int)log2(jumpto)][1] ; diff-=jumpto ; }*/ //reached the common level for(int j=19;j>=0;j--)//20 { int av = dp[v][j][0] ; int uv = dp[u][j][0] ; if(av!=uv) { dist+=dp[v][j][1]+dp[u][j][1] ;//jumping simultaneously upwards v = av ; u = uv ; } } //parent of u and v is the lca dist+=dp[v][0][1]+dp[u][0][1] ; cout<<max(maxD,dist)<<"\n" ; } } } /* 1 7 3 1 2 1 1 3 -2 2 4 3 2 5 -4 5 7 5 3 6 6 2 3 1 5 4 2 5 6 0 Expected answer: 10 7 5 */
Теги #codechef, lca, #trees, #tutorial

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en11 Английский Mooncrater 2020-02-02 13:14:35 1934 Tiny change: '\nHello all,' -> 'Hello all,'
en10 Английский Mooncrater 2020-02-02 13:06:10 2 Tiny change: 'fine MAXN 200005\n\nt' -> 'fine MAXN 300005\n\nt'
en9 Английский Mooncrater 2020-02-02 13:04:47 4 Tiny change: '--------\n**EDIT 2' -> '--------\n\n\n**EDIT 2'
en8 Английский Mooncrater 2020-02-02 13:04:28 294
en7 Английский Mooncrater 2020-02-02 11:35:48 98
en6 Английский Mooncrater 2020-02-02 11:34:28 673
en5 Английский Mooncrater 2020-02-02 10:54:45 147
en4 Английский Mooncrater 2020-02-02 10:53:25 5
en3 Английский Mooncrater 2020-02-02 10:53:06 78 TLE - > WA
en2 Английский Mooncrater 2020-02-02 10:24:43 260 TLE --> WA
en1 Английский Mooncrater 2020-02-02 10:00:53 7049 Initial revision (published)