Dang_Quan_10_Tin

B

Jul 22nd, 2020
255
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
CSS 2.28 KB | None | 0 0
  1.  
  2. // HOC HANH NHU CAI DAU KHAC
  3.  
  4. #include <iostream>
  5. #include <cstdio>
  6. #include <vector>
  7. #include <unordered_map>
  8. #include <set>
  9. #include <map>
  10. #define task "TESTs"
  11. using namespace std;
  12. using ll = long long;
  13. using ld = long double;
  14.  
  15. const int N = 2e5 + 3;
  16. vector<pair<int, ll>> adj[N];
  17. int now[N], then[N];
  18. int n, m, l, q;
  19. int a[N], b[N];
  20. int par[20][N];
  21. int ranks[N];
  22. int last[N];
  23. ll st[N], z[N], d[N];
  24.  
  25. void Read(){
  26.     cin >> n >> q;
  27.     for(int i = 1; i < n; ++i){
  28.         ll c;
  29.         cin >> a[i] >> b[i] >> z[i];
  30.         adj[a[i]].push_back({b[i], z[i]});
  31.         adj[b[i]].push_back({a[i], z[i]});
  32.     }
  33. }
  34.  
  35. /// --- DFS DECOMPOSITION --- ///
  36. ///                  - Ft. LCA - ///
  37.  
  38. void dfs(int v){
  39.     now[v] = ++m;
  40.     then[m] = v;
  41.     last[now[v]] = now[v];
  42.     for(auto i : adj[v]){
  43.         if(ranks[i.first] != 0)
  44.             continue;
  45.         ranks[i.first] = ranks[v] + 1;
  46.         d[i.first] = d[v] + i.second;
  47.         par[0][i.first] = v;
  48.         dfs(i.first);
  49.         last[now[v]] = max(last[now[v]], last[now[i.first]]);
  50.     }
  51. }
  52.  
  53. void LCA(){
  54.     for(int i = 1; i <= 18; ++i)
  55.         for(int j = 1; j <= n; ++j)
  56.             par[i][j] = par[i - 1][par[i - 1][j]];
  57. }
  58.  
  59. int find_par(int u, int v){
  60.     if(ranks[u] < ranks[v])
  61.         swap(u, v);
  62.     for(int i = 18; ~i; --i)
  63.         if(par[i][u] > 0 && ranks[par[i][u]] >= ranks[v])
  64.             u = par[i][u];
  65.     if(u == v)
  66.         return u;
  67.     for(int i = 18; ~i; --i)
  68.         if(par[i][u] != par[i][v]){
  69.             u = par[i][u];
  70.             v = par[i][v];
  71.         }
  72.     while(u != v)
  73.         u = par[0][u],
  74.         v = par[0][v];
  75.     return u;
  76. }
  77.  
  78. void upd(int pos, ll v){
  79.     for(int i = pos; i <= n; i += i & -i)
  80.         st[i] += v;
  81. }
  82.  
  83. ll que(int pos){
  84.     ll ans = 0;
  85.     for(int i = pos; i > 0; i -= i & -i)
  86.         ans += st[i];
  87.     return ans;
  88. }
  89.  
  90. void Solve(){
  91.     while(q--){
  92.         int t;
  93.         cin >> t;
  94.         if(t == 1){
  95.             int i;
  96.             ll x;
  97.             cin >> i >> x;
  98.             int beg = max(now[a[i]], now[b[i]]);
  99.             int en = last[beg];
  100.             upd(beg, x - z[i]);
  101.             upd(en + 1, z[i] - x);
  102.             z[i] = x;
  103.         }
  104.         else{
  105.             int u, v;
  106.             cin >> u >> v;
  107.             ll ans = 0;
  108.             int h = find_par(u, v);
  109.             cout << que(now[u]) + d[u] + que(now[v]) + d[v] - 2ll * (que(now[h]) + d[h]) << "\n";
  110.         }
  111.     }
  112. }
  113.  
  114. main(){
  115.     ios::sync_with_stdio(0);
  116.     cin.tie(0);
  117.     cout.tie(0);if(fopen(task".INP", "r"))
  118.     freopen(task".INP", "r", stdin),
  119.     freopen(task".OUT", "w", stdout);
  120.     Read();
  121.     ranks[1] = 1;
  122.     dfs(1);
  123.     LCA();
  124.     Solve();
  125. }
Advertisement
Add Comment
Please, Sign In to add comment