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 in two ways (in my opinion):
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.Move LSB to MSB. That is, 2^1st parent, then from there, 2^2nd parent, and from there 2^3rd parent. And v'oil'a, we're there, as the total remains the same. This is what I thought of. The first method is sure shot correct, but this one might not be so, plz do chek.
Good. Now we're at the same level, now we go up up and away, until we can't. Then we current nodes' parent is the LCA. We kept on putting the distance in our dist variable which we can use to update the maxD variable, which is our answer.
I do not understand why am I getting a TLE in this. I mean a WA would be okay, and acceptable. A TLE? I mean whut. I've elaborated this a little bit more, but only to make sure no one has to do a lot to understand what's going on. There could be a very silly mistake in here, and I don't want anyone other than me to give in much time for that.
Plz halp I'm dying in shame.
#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 200005
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 ;
depth[node] = depth[par]+1 ;
for(auto x:al[node])
if(x.X!=par)
{
dp[x.X][0][0] = node ;
dp[x.X][0][1] = x.Y ;
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)
{
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)) ;
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[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)) ;
v = dp[v][jumpto][0] ;
dist+=dp[v][jumpto][1] ;
diff -= (1<<jumpto) ;
}*/
while(diff)
{
int jumpto = diff&(-diff) ;
v = dp[v][jumpto][0] ;
dist+=dp[v][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
*/
