YEZAELP

TUMSO-16: Ant Colony

Dec 4th, 2021
667
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using lli = long long;
  5. using pll = pair <lli, lli>;
  6. const lli maxN = 1e5;
  7. const lli logN = log2(maxN);
  8. vector <pll> g[maxN + 10];
  9. lli level[maxN + 10], par[maxN + 10][logN + 10], dis[maxN + 10][logN + 10];
  10. lli n;
  11.  
  12. void dfs(lli u, lli p, lli lvl, lli pw){
  13.     level[u] = lvl;
  14.     par[u][0] = p;
  15.     dis[u][0] = pw;
  16.     for(auto vw: g[u]){
  17.         lli v = vw.first;
  18.         lli w = vw.second;
  19.         if(v != p){
  20.             dfs(v, u, lvl + 1, w);
  21.         }
  22.     }
  23. }
  24.  
  25. lli LCA_Dis(lli u, lli v){ /// u -> v
  26.     if(level[u] < level[v]) swap(u, v);
  27.     lli sum = 0;
  28.     for(lli e=logN;e>=0;e--){
  29.         if(level[ par[u][e] ] >= level[v]){
  30.             sum += dis[u][e];
  31.             u = par[u][e];
  32.         }
  33.     }
  34.     if(u == v) return sum;
  35.     for(lli e=logN;e>=0;e--){
  36.         if(par[u][e] != par[v][e]){
  37.             sum += dis[u][e];
  38.             u = par[u][e];
  39.             sum += dis[v][e];
  40.             v = par[v][e];
  41.         }
  42.     }
  43.     sum += dis[u][0];
  44.     sum += dis[v][0];
  45.     return sum;
  46. }
  47.  
  48. int main(){
  49.  
  50.     scanf("%lld", &n);
  51.  
  52.     for(lli u=1;u<=n-1;u++){
  53.         lli v, w;
  54.         scanf("%lld %lld", &v, &w);
  55.         g[u].push_back({v, w});
  56.         g[v].push_back({u, w});
  57.     }
  58.  
  59.     dfs(0, 0, 1, 0);
  60.  
  61.     for(lli e=1;e<=logN;e++){
  62.         for(lli u=0;u<=n;u++){
  63.             par[u][e] = par[ par[u][e - 1] ][e - 1];
  64.             dis[u][e] = dis[u][e - 1] + dis[ par[u][e - 1] ][e - 1];
  65.         }
  66.     }
  67.  
  68.     lli q;
  69.     scanf("%lld", &q);
  70.  
  71.     while(q--){
  72.         lli u, v;
  73.         scanf("%lld %lld", &u, &v);
  74.         printf("%lld\n", LCA_Dis(u, v));
  75.     }
  76.  
  77.     return 0;
  78. }
  79.  
RAW Paste Data