YEZAELP

o25_oct_ringroad

Jan 6th, 2022 (edited)
856
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 pii = pair <int, int>;
  6. const int N = 2e5 + 5;
  7. vector <pii> g[N];
  8. lli dis[N], qs[N];
  9. int in_sect[N];
  10. int n, k, Q;
  11.  
  12. void Update(int pst, int val){
  13.     for(int i=pst;i<=k;i+=i&-i)
  14.         dis[i] += (lli) val;
  15. }
  16.  
  17. lli Sum(int pst, lli sum = 0){
  18.     for(int i=pst;i>=1;i-=i&-i)
  19.         sum += dis[i];
  20.     return sum;
  21. }
  22.  
  23. lli RangeSum(int s, int e){
  24.     return Sum(e) - Sum(s - 1);
  25. }
  26.  
  27. lli Ring(int u, int v){
  28.     if(u > v) swap(u, v);
  29.     lli a = RangeSum(u, v - 1);
  30.     lli b = RangeSum(1, u - 1) + RangeSum(v, k);
  31.     return min(a, b);
  32. }
  33.  
  34. void dfs(int cur, int u, int p, lli d){
  35.     qs[u] = d;
  36.     in_sect[u] = cur;
  37.     for(auto vw: g[u]){
  38.         int v = vw.first;
  39.         int w = vw.second;
  40.         if(v != p)
  41.             dfs(cur, v, u, d + (lli) w);
  42.     }
  43. }
  44.  
  45. lli Same(int u, int v){
  46.     return abs(qs[u] - qs[v]);
  47. }
  48.  
  49. int main(){
  50.  
  51.     scanf("%d %d %d", &n, &k, &Q);
  52.  
  53.     for(int i=1;i<=k;i++){
  54.         int w;
  55.         scanf("%d", &w);
  56.         Update(i, w);
  57.     }
  58.  
  59.     for(int u=k+1;u<=n;u++){
  60.         int v, w;
  61.         scanf("%d %d", &v, &w);
  62.         g[u].push_back({v, w});
  63.         g[v].push_back({u, w});
  64.     }
  65.  
  66.     for(int u=1;u<=k;u++){
  67.         dfs(u, u, u, 0);
  68.     }
  69.  
  70.     for(int q=1;q<=Q;q++){
  71.         int opr;
  72.         scanf("%d", &opr);
  73.         if(opr == 0){
  74.             int u, w;
  75.             scanf("%d %d", &u, &w);
  76.             Update(u, -RangeSum(u, u));
  77.             Update(u, w);
  78.         }
  79.         else if(opr == 1){
  80.             int u, v;
  81.             scanf("%d %d", &u, &v);
  82.             if(in_sect[u] == in_sect[v]) printf("%lld\n", Same(u, v));
  83.             else {
  84.                 printf("%lld\n", qs[u] + qs[v] + Ring(in_sect[u], in_sect[v]));
  85.             }
  86.         }
  87.     }
  88.  
  89.     return 0;
  90. }
RAW Paste Data Copied