ccbeginner

CODECHEF TAQTREE

Mar 3rd, 2020
133
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //CODECHEF TAQTREE
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int n,q;
  6. vector<int> v[100001], w[100001];
  7. struct edge{
  8.     int U, V, W;
  9. }e[100001];
  10. ////////////////////////////////////////////LCA part
  11. const int bnd = 18;//the max(logn)
  12. int F[100001][bnd];//lca form
  13. int depth[100001];
  14.  
  15. void make(int d, int u, int pre){
  16.     depth[u] = d;
  17.     F[u][0] = pre;
  18.     for(int i = 1; i < bnd; ++i)F[u][i] = F[F[u][i-1]][i-1];
  19.     for(int i = 0; i < v[u].size(); ++i){
  20.         if(v[u][i] != pre)make(d+1, v[u][i], u);
  21.     }
  22. }
  23.  
  24. int lca(int u, int v){
  25.     if(depth[u] > depth[v])swap(u, v);//make sure depth[u] <= depth[v]
  26.     for(int i = bnd-1; i >= 0 && depth[u] != depth[v]; --i){
  27.         if(depth[v] - depth[u] >= (1<<i))v = F[v][i];
  28.     }
  29.     if(u == v)return u;
  30.     for(int i = bnd-1; i >= 0; --i){
  31.         if(F[u][i] != F[v][i]){
  32.             u = F[u][i];
  33.             v = F[v][i];
  34.         }
  35.     }
  36.     return F[u][0];
  37. }
  38. ////////////////////////////////////////////BIT part
  39. int BIT[200001];
  40.  
  41. void addv(int k, int val){//change the value at node (k)
  42.     while(k <= 2*n){
  43.         BIT[k] += val;
  44.         k += (k & -k);
  45.     }
  46. }
  47.  
  48. int getv(int k){//get distance from node (k) to node (1)
  49.     int ret = 0;
  50.     while(k){
  51.         ret += BIT[k];
  52.         k -= (k & -k);
  53.     }
  54.     return ret;
  55. }
  56. ////////////////////////////////////////////DFS part
  57. //using euler traversal
  58. int cnt = 0;
  59. int in[100001], out[100001];//dfs orders
  60.  
  61. void dfs(int u, int pre, int val){//val is the weight to parent
  62.     in[u] = ++cnt;
  63.     addv(in[u], val);
  64.     for(int i = 0; i < v[u].size(); ++i){
  65.         if(v[u][i] != pre)dfs(v[u][i], u, w[u][i]);
  66.     }
  67.     out[u] = ++cnt;
  68.     addv(out[u], -val);
  69. }
  70. ////////////////////////////////////////////main part
  71. int32_t main(){
  72.     cin >> n;
  73.     for(int i = 1; i < n; ++i){
  74.         int a,b,c;
  75.         cin >> a >> b >> c;
  76.         v[a].emplace_back(b);
  77.         v[b].emplace_back(a);
  78.         w[a].emplace_back(c);
  79.         w[b].emplace_back(c);
  80.         e[i] = {.U = a, .V = b, .W = c};
  81.     }
  82.     dfs(1, 0, 0);//root = 1, parent = 0, weight to parent = 0
  83.     make(1, 1, 0);//root depth = 1, root = 1, parent = 0
  84.     cin >> q;
  85.     while(q--){
  86.         int a,b,c;
  87.         cin >> a >> b >> c;
  88.         if(a == 1){
  89.             int addw = c - e[b].W;
  90.             if(depth[e[b].U] > depth[e[b].V])swap(e[b].U, e[b].V);
  91.             addv(in[e[b].V], addw);
  92.             addv(out[e[b].V], -addw);
  93.         }else if(a == 2){
  94.             int parent = lca(b, c);
  95.             cout << getv(in[b]) + getv(in[c]) - 2 * getv(in[parent]) << '\n';
  96.         }
  97.     }
  98.     return 0;
  99. }
RAW Paste Data