Advertisement
Vince14

/<> 13510 (Heavy-Light Decomposition)

Oct 7th, 2023 (edited)
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.87 KB | Source Code | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <vector>
  7. #include <set>
  8. #include <map>
  9. #include <stack>
  10. #include <queue>
  11. #include <deque>
  12. #include <unordered_map>
  13. #include <numeric>
  14. #include <iomanip>
  15. using namespace std;
  16. #define pii pair<int , int>
  17. #define ll long long
  18. #define FAST ios_base::sync_with_stdio(false); cin.tie(NULL)
  19. const long long dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
  20. const long long dl[2] = {1, -1};
  21. const long long MOD = 1000000007;
  22. const long long MAXN = 100005;
  23.  
  24.  
  25. int N, M, sz[MAXN], par[MAXN], dep[MAXN], heavy[MAXN], idx[MAXN], head[MAXN], seg[MAXN * 4], cost[MAXN], tmp_cost[MAXN], cur_idx = 1;
  26. pair<pii, int> edge[MAXN];
  27. int child_of[MAXN];
  28. vector<pii> v[MAXN];
  29.  
  30. void dfs(int cur, int p, int d){
  31.     int max_sz = 0;
  32.     int max_c = -1;
  33.     sz[cur] = 1;
  34.     par[cur] = p;
  35.     dep[cur] = d;
  36.     for(auto x : v[cur]){
  37.         if(x.first != p){
  38.             tmp_cost[x.first] = x.second;
  39.             dfs(x.first, cur, d + 1);
  40.             sz[cur] += sz[x.first];
  41.             if(sz[x.first] > max_sz){
  42.                 max_sz = sz[x.first];
  43.                 max_c = x.first;
  44.             }
  45.         }
  46.     }
  47.     heavy[cur] = max_c;
  48. }
  49.  
  50. void decompose(int cur, int h){
  51.     head[cur] = h;
  52.     idx[cur] = cur_idx;
  53.     cost[idx[cur]] = tmp_cost[cur];
  54.     cur_idx++;
  55.     if(heavy[cur] != -1){
  56.         decompose(heavy[cur], h);
  57.     }
  58.     for(auto x : v[cur]){
  59.         if(x.first != par[cur] && x.first != heavy[cur]){
  60.             decompose(x.first, x.first);
  61.         }
  62.     }
  63. }
  64.  
  65. void build(int x, int s, int e){
  66.     if(s == e){
  67.         seg[x] = cost[s];
  68.         return;
  69.     }
  70.     int mid = (s + e)/2;
  71.     build(x * 2, s, mid);
  72.     build(x * 2 + 1, mid + 1, e);
  73.     seg[x] = max(seg[x * 2], seg[x * 2 + 1]);
  74. }
  75.  
  76. void update(int x, int s, int e, int id, int val){
  77.     if(id < s || e < id) return;
  78.     if(s == e){
  79.         seg[x] = val;
  80.         return;
  81.     }
  82.     int mid = (s + e)/2;
  83.     update(x * 2, s, mid, id, val);
  84.     update(x * 2 + 1, mid + 1, e, id, val);
  85.     seg[x] = max(seg[x * 2], seg[x * 2 + 1]);
  86. }
  87.  
  88. int query(int x, int s, int e, int a, int b){
  89.     if(b < s || e < a) return 0;
  90.     if(a <= s && e <= b){
  91.         return seg[x];
  92.     }
  93.     int mid = (s + e)/2;
  94.     return max(query(x * 2, s, mid, a, b), query(x * 2 + 1, mid + 1, e, a, b));
  95. }
  96.  
  97. int solve(int a, int b){
  98.     int ret = 0;
  99.     while(head[a] != head[b]){
  100.         if(dep[head[a]] > dep[head[b]]) swap(a, b);
  101.         ret = max(ret, query(1, 1, N, idx[head[b]], idx[b]));
  102.         b = par[head[b]];
  103.     }
  104.     if(dep[a] > dep[b]){
  105.         swap(a, b);
  106.     }
  107.     ret = max(ret, query(1, 1, N, idx[a] + 1, idx[b]));
  108.     return ret;
  109. }
  110.  
  111.  
  112.  
  113. int main() {
  114.     FAST;
  115.     cin >> N;
  116.     for(int i = 1; i < N; i++){
  117.         cin >> edge[i].first.first >> edge[i].first.second >> edge[i].second;
  118.         v[edge[i].first.first].push_back({edge[i].first.second, edge[i].second});
  119.         v[edge[i].first.second].push_back({edge[i].first.first, edge[i].second});
  120.     }
  121.     dfs(1, 0, 1);
  122.     decompose(1, 1);
  123.     build(1, 1, N);
  124.     for(int i = 1; i < N; i++){
  125.         if(par[edge[i].first.first] == edge[i].first.second){
  126.             child_of[i] = edge[i].first.first;
  127.         }
  128.         else{
  129.             child_of[i] = edge[i].first.second;
  130.         }
  131.     }
  132.     cin >> M;
  133.     for(int x, y, z, i = 0; i < M; i++){
  134.         cin >> x >> y >> z;
  135.         if(x == 1){
  136.             int ver = child_of[y];
  137.             update(1, 1, N, idx[ver], z);
  138.         }
  139.         else{
  140.             if(y == z){
  141.                 cout << "0\n";
  142.             }
  143.             else{
  144.                 cout << solve(y, z) << "\n";
  145.             }
  146.         }
  147.     }
  148. }
  149.  
  150. /*
  151. 3
  152. 1 2 1
  153. 2 3 2
  154. 3
  155. 2 1 2
  156. 1 1 3
  157. 2 1 2
  158.  */
  159.  
  160. /*
  161. 13
  162.  1 2 1
  163.  1 3 2
  164.  2 4 3
  165.  2 5 4
  166.  3 6 5
  167.  5 7 6
  168.  5 8 7
  169.  6 9 8
  170.  6 10 9
  171.  9 11 10
  172.  9 12 11
  173.  10 13 12
  174.  */
  175.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement