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:
And the distance recurrence is:
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 rootmcd: 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 ofdp, runningdfs1, running a loop for each query et cetera. In the loop, we get the answer for the case 2, intmaxDinitially. Then we calculate the answer for the case 1. If the two nodes are not at the samelevel, then we can we bring them on the same level. Let's assume they have a difference ofdiffin 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
*/
