Processing math: 100%

TLE in codechef's TREEEDGE (LCA using binary lifting). Halp

Revision en1, by Mooncrater, 2020-02-02 10:00:53

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][parent1]][parent1]

And the distance recurrence is:

distance[node][parent]=distance[node][parent1]+distance[dp[node][parent1]][parent1]

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 ualpha is the node in u's subtree that is farthest from u, and vα 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α)+dist(v,vα)+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 2jth parent of i

  • dp[i][j][1]: Saves the distance of the 2jth 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(logN) operation in my opinion.( Not opinion, I know but humble++). This can be done in two ways (in my opinion):
  1. 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.

  2. 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.

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 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 */
Tags #codechef, lca, #trees, #tutorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en11 English Mooncrater 2020-02-02 13:14:35 1934 Tiny change: '\nHello all,' -> 'Hello all,'
en10 English Mooncrater 2020-02-02 13:06:10 2 Tiny change: 'fine MAXN 200005\n\nt' -> 'fine MAXN 300005\n\nt'
en9 English Mooncrater 2020-02-02 13:04:47 4 Tiny change: '--------\n**EDIT 2' -> '--------\n\n\n**EDIT 2'
en8 English Mooncrater 2020-02-02 13:04:28 294
en7 English Mooncrater 2020-02-02 11:35:48 98
en6 English Mooncrater 2020-02-02 11:34:28 673
en5 English Mooncrater 2020-02-02 10:54:45 147
en4 English Mooncrater 2020-02-02 10:53:25 5
en3 English Mooncrater 2020-02-02 10:53:06 78 TLE - > WA
en2 English Mooncrater 2020-02-02 10:24:43 260 TLE --> WA
en1 English Mooncrater 2020-02-02 10:00:53 7049 Initial revision (published)