Mooncrater's blog

By Mooncrater, history, 4 years ago, In English

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 */
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I really appreciate how you have explained your code, not just "plz help find misktake". Mayne a bit much, but eh.

Do you ever clear the al vector between test cases? I think what happens is that in the next test case, you add new edges to the ones from the last test, your tree isn't a tree anymore and the dfs gets stuck in a loop.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks Mayne! There was a problem with that. I changed that. Now I'm getting the acceptable WA. I'm looking into it in depth to understand what's the problem. Do tell if you find something awry.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Finally. There were two three minor bugs. Thanks for the help!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Mooncrater (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Mooncrater (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Mooncrater (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Mooncrater (previous revision, new revision, compare).

»
4 years ago, # |
Rev. 3   Vote: I like it -10 Vote: I do not like it

.