fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long 
  3. #define endl '\n'
  4. #define MASK(n) (1 << n)
  5. #define pp pair<int,pair<int,int>>
  6. #define PhTrNghia "TASK"
  7.  
  8. using namespace std;
  9.  
  10. const int maxn = 1e5 + 5;
  11. const int inf = 1e18;
  12.  
  13. struct segment_tree{
  14.     struct node{
  15.         int mn, mx;
  16.         bool lazy;
  17.         node(){
  18.             mn = inf;
  19.             mx = -inf;
  20.             lazy = 0;
  21.         }
  22.     };
  23.  
  24.     int n;
  25.     vector <node> tree;
  26.     segment_tree(int _n){
  27.         n = _n;
  28.         tree.assign(n << 2 | 5, node());
  29.     }
  30.  
  31.     void apply(int id){
  32.         swap(tree[id].mn, tree[id].mx);
  33.         tree[id].mn *= -1;
  34.         tree[id].mx *= -1;
  35.         tree[id].lazy ^= 1;
  36.     }
  37.  
  38.     void push_down(int id){
  39.         if (tree[id].lazy){
  40.             apply(id << 1);
  41.             apply(id << 1 | 1);
  42.             tree[id].lazy = 0;
  43.         }
  44.     }
  45.  
  46.     void update(int id, int l, int r, int pos, int val){
  47.         if (l > pos or r < pos) return;
  48.         if (l == r){ 
  49.             tree[id].mn = val;
  50.             tree[id].mx = val;
  51.             return; 
  52.         }
  53.         int mid = (l + r) >> 1;
  54.         push_down(id);
  55.         update(id << 1, l, mid, pos, val);
  56.         update(id << 1 | 1, mid + 1, r, pos, val);
  57.         tree[id].mn = min(tree[id << 1].mn, tree[id << 1 | 1].mn);
  58.         tree[id].mx = max(tree[id << 1].mx, tree[id << 1 | 1].mx);
  59.     }
  60.  
  61.     void flip(int id, int l, int r, int u, int v){
  62.         if (l > v or r < u) return;
  63.         if (l >= u && r <= v){
  64.             apply(id);
  65.             return;
  66.         }
  67.         int mid = (l + r) >> 1;
  68.         push_down(id);
  69.         flip(id << 1, l, mid, u, v);
  70.         flip(id << 1 | 1, mid + 1, r, u, v);
  71.         tree[id].mn = min(tree[id << 1].mn, tree[id << 1 | 1].mn);
  72.         tree[id].mx = max(tree[id << 1].mx, tree[id << 1 | 1].mx);
  73.     }
  74.  
  75.     int get(int id, int l, int r, int u, int v){
  76.         if (l > v or r < u) return -inf;
  77.         if (l >= u && r <= v) return tree[id].mx;
  78.         int mid = (l + r) >> 1;
  79.         push_down(id);
  80.         int get1 = get(id << 1, l, mid, u, v);
  81.         int get2 = get(id << 1 | 1, mid + 1, r, u, v);
  82.         return max(get1, get2);
  83.     }
  84.  
  85.     void update(int pos, int val){
  86.         update(1, 1, n, pos, val);
  87.     }
  88.  
  89.     void flip(int l, int r){
  90.         flip(1, 1, n, l, r);
  91.     }    
  92.  
  93.     int get(int l, int r){
  94.         return get(1, 1, n, l, r);
  95.     }
  96. };
  97.  
  98. int n, q;
  99. vector <pair <int, int>> g[maxn];
  100. int sz[maxn], bigC[maxn], bigW[maxn], parent[maxn], dep[maxn], head[maxn], op[maxn], cnt = 0;
  101.  
  102. void pre_dfs(int u, int p){
  103.     sz[u] = 1;
  104.     parent[u] = p;
  105.     dep[u] = dep[p] + 1;
  106.     for (pair <int, int> cur: g[u]){
  107.         int v = cur.first;
  108.         int w = cur.second;
  109.         if (v == p) continue;
  110.         pre_dfs(v, u);
  111.         sz[u] += sz[v];
  112.         if (sz[bigC[u]] < sz[v]){ 
  113.             bigC[u] = v;
  114.             bigW[u] = w;
  115.         }    
  116.     }
  117. }
  118.  
  119. segment_tree smt(maxn);
  120.  
  121. void hld(int u, int p, int w, int top){
  122.     head[u] = top;
  123.     op[u] = ++cnt;
  124.     smt.update(cnt, w);
  125.  
  126.     if (bigC[u]) hld(bigC[u], u, bigW[u], top);
  127.  
  128.     for (pair <int, int> cur: g[u]){
  129.         int v = cur.first;
  130.         int ww = cur.second;
  131.         if (v == p or v == bigC[u]) continue;
  132.         hld(v, u, ww, v);
  133.     }
  134. }
  135.  
  136. pair <int, int> edges[maxn];
  137.  
  138. void hld_update(int pos, int val){
  139.     int node = edges[pos].second;
  140.     smt.update(op[node], val);
  141. }
  142.  
  143. void hld_flip(int u, int v){
  144.     while (head[u] != head[v]){
  145.         if (dep[head[u]] < dep[head[v]]) swap(u, v);
  146.         smt.flip(op[head[u]], op[u]);
  147.         u = parent[head[u]];
  148.     }
  149.     if (dep[u] > dep[v]) swap(u, v);
  150.     smt.flip(op[u] + 1, op[v]);
  151. }
  152.  
  153. int hld_get(int u, int v){
  154.     int res = -inf;
  155.     while (head[u] != head[v]){
  156.         if (dep[head[u]] < dep[head[v]]) swap(u, v);
  157.         res = max(res, smt.get(op[head[u]], op[u]));
  158.         u = parent[head[u]];
  159.     }
  160.     if (dep[u] > dep[v]) swap(u, v);
  161.     res = max(res, smt.get(op[u] + 1, op[v]));
  162.     return res;
  163. }
  164.  
  165. signed main(){
  166.     ios_base::sync_with_stdio(false);
  167.     cin.tie(0); cout.tie(0);
  168.     if (fopen(PhTrNghia".INP", "r")){
  169.         freopen(PhTrNghia".INP", "r", stdin);
  170.         freopen(PhTrNghia".OUT", "w", stdout);
  171.     }
  172.  
  173.     cin >> n >> q;
  174.     for (int i = 1; i < n; i++){
  175.         int x, y, w;
  176.         cin >> x >> y >> w;
  177.         edges[i] = {x, y};
  178.         g[x].push_back({y, w});
  179.         g[y].push_back({x, w});
  180.     }
  181.  
  182.     pre_dfs(1, 0);
  183.     hld(1, 0, 0, 1);
  184.  
  185.     for (int i = 1; i < n; i++){
  186.         int x = edges[i].first;
  187.         int y = edges[i].second;
  188.         if (dep[x] > dep[y]) swap(edges[i].first, edges[i].second);
  189.     }
  190.  
  191.     while (q--){
  192.         string type;
  193.         cin >> type;
  194.         if (type == "CHANGE"){
  195.             int pos, val;
  196.             cin >> pos >> val;
  197.             hld_update(pos, val);
  198.         }
  199.  
  200.         if (type == "NEGATE"){
  201.             int u, v;
  202.             cin >> u >> v;
  203.             hld_flip(u, v);
  204.         }
  205.  
  206.         if (type == "QUERY"){
  207.             int u, v;
  208.             cin >> u >> v;
  209.             cout << hld_get(u, v) << endl;
  210.         }
  211.     }
  212.  
  213.     return 0;
  214. }
Success #stdin #stdout 0.01s 20500KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2ymMT6
language:
C++14 (gcc 8.3)
created:
16 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!