Can anyone share the editorial of tree path sum

#1

https://www.codechef.com/CCHI2021/problems/CCBTS05

#2

Read about Binary Lifting from here. And then refer to this code you’ll get the idea.

CODE 
#include "bits/stdc++.h"
#define int long long 
using namespace std ;
const int mxN = 1e5+2 ;
vector<int> adj[mxN] ;
int anc[mxN][18],d[mxN],n,m,ps[mxN],r,q,ev[mxN],eu[mxN],ew[mxN];
void dfs(int v,int p){
  anc[v][0]=p ;d[v]=d[p]+1 ;
  for(int i=1;i<18;i++)
    anc[v][i]=~anc[v][i-1]?anc[anc[v][i-1]][i-1]:-1 ;
  for(int x:adj[v]){
    int u =(v^eu[x]^ev[x]) ;
    if(u==p)
      continue  ;
    ps[u]=ps[v]+ew[x] ;
    dfs(u,v) ;
  }
}
int lca(int u,int v){
  if(d[u]<d[v])
    swap(u,v) ;
  for(int i=17;~i;--i)
    if(d[u]-(1<<i)>=d[v])
      u=anc[u][i] ;
  if(u==v)
    return u ;
  for(int i =17;~i;--i)
    if(anc[u][i]^anc[v][i])
      u=anc[u][i],v=anc[v][i] ;
return anc[u][0] ;
}
void solve(){		
  cin>>n>>q>>r ;
  for(int i=0;i<n-1;i++){
    cin>>eu[i]>>ev[i]>>ew[i];
    adj[ev[i]].push_back(i) ;
    adj[eu[i]].push_back(i) ;
  }
  ps[r]=0;dfs(r,0) ;
  while(q--){
    int a,b;cin>>a>>b;
    cout<< ps[a]+ps[b]-2*ps[lca(a,b)] <<'\n' ;
  }
  for(int i=1;i<n+1;i++)
    adj[i].clear();
}
signed main(){	
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); 	
  int TC  ;
  cin>>TC ;
  while(TC--)
    solve() ;
}
1 Like
#3

thanks

1 Like