Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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
- 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
- */
Add Comment
Please, Sign In to add comment