fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define maxn 10004
  4. #define file
  5. #define inf 1000000000
  6.  
  7. int t;
  8.  
  9. int n;
  10. struct edge {
  11.     int u,v,w;
  12. }edges[maxn];
  13. vector<pair<int,int> > g[maxn];
  14. int val[maxn];
  15. int par[20][maxn],sz[maxn],h[maxn];
  16.  
  17. void dfs (int u,int p) {
  18.     sz[u]++;
  19.     for (auto x : g[u]) {
  20.         int v = x.first;
  21.         int w = x.second;
  22.         if (v == p) continue;
  23.         par[0][v] = u;
  24.         val[v] = w;
  25.         h[v] = h[u] + 1;
  26.         for (int i=1;i<20;i++) par[i][v] = par[i-1][par[i-1][v]];
  27.         dfs(v,u);
  28.         sz[u] += sz[v];
  29.     }
  30. }
  31.  
  32. int LCA (int u,int v) {
  33.     if (h[u] < h[v]) swap(u,v);
  34.     int d = h[u] - h[v];
  35.     for (int i=19;i>=0;i--) if ((d>>i) & 1) u = par[i][u];
  36.     if (u == v) return u;
  37.     for (int i=19;i>=0;i--) if (par[i][u] != par[i][v]) {
  38.         u = par[i][u];
  39.         v = par[i][v];
  40.     }
  41.     return par[0][u];
  42. }
  43.  
  44. int head[maxn],pos[maxn],cur_p;
  45. void hld (int u,int root) {
  46.     if (!head[u]) head[u] = root;
  47.     pos[u] = ++cur_p;
  48.  
  49.     int heavy = 0;
  50.     for (auto x : g[u]) {
  51.         int v = x.first;
  52.         if (v == par[0][u]) continue;
  53.         if (!heavy || sz[v] > sz[heavy]) heavy = v;
  54.     }
  55.     if (heavy) hld(heavy,root);
  56.     for (auto x : g[u]) {
  57.         int v = x.first;
  58.         if (v == par[0][u] || v == heavy) continue;
  59.         hld(v,v);
  60.     }
  61. }
  62.  
  63. struct node {
  64.     int ma,mi,lazy;
  65. }st[maxn * 4];
  66. void push (int id) {
  67.     if (st[id].lazy == -1){
  68.         st[id * 2].ma *= st[id].lazy;
  69.         st[id * 2].mi *= st[id].lazy;
  70.         st[id * 2].lazy *= st[id].lazy;
  71.         st[id * 2 + 1].ma *= st[id].lazy;
  72.         st[id * 2 + 1].mi *= st[id].lazy;
  73.         st[id * 2 + 1].lazy *= st[id].lazy;
  74.         swap(st[id * 2].ma,st[id * 2].mi);
  75.         swap(st[id * 2 + 1].ma,st[id * 2 + 1].mi);
  76.         st[id].lazy = 1;
  77.     }
  78. }
  79. node mer (const node& x,const node& y) {
  80.     return {max(x.ma,y.ma),min(x.mi,y.mi),1};
  81. }
  82. void change (int id,int l,int r,int p,int v) {
  83.     if (l == r) {
  84.         st[id].ma = v;
  85.         st[id].mi = v;
  86.         return ;
  87.     }
  88.     push(id);
  89.     int mid = (l + r) >> 1;
  90.     if (p <= mid) change(id * 2,l,mid,p,v);
  91.     else change(id * 2 + 1,mid + 1,r,p,v);
  92.     st[id] = mer(st[id * 2], st[id * 2 + 1]);
  93. }
  94. void neg(int id,int l,int r,int u,int v) {
  95.     if (u > v) swap(u,v);
  96.     if (u > r || l > v) return ;
  97.     if (u <= l && r <= v) {
  98.         st[id].ma *= -1;
  99.         st[id].mi *= -1;
  100.         st[id].lazy *= -1;
  101.         swap(st[id].ma,st[id].mi);
  102.         return ;
  103.     }
  104.     push(id);
  105.     int mid = (l + r) >> 1;
  106.     neg(id * 2,l,mid,u,v);
  107.     neg(id * 2 + 1,mid + 1,r,u,v);
  108.     st[id] = mer(st[id * 2],st[id * 2 + 1]);
  109. }
  110. node getmax (int id,int l,int r,int u,int v) {
  111.     if (u > v) swap(u,v);
  112.     if (u > r || l > v) return {-inf,inf,1};
  113.     if (u <= l && r <= v) return st[id];
  114.     push(id);
  115.     int mid = (l + r) >> 1;
  116.     return mer (getmax(id * 2,l,mid,u,v), getmax(id * 2 + 1,mid + 1,r,u,v));
  117. }
  118.  
  119. int main(){
  120.     ios_base::sync_with_stdio(false);
  121.     cin.tie(0);cout.tie(0);
  122.     if (fopen(file".INP","r")) {
  123.         freopen(file".INP","r",stdin);
  124.         freopen(file".OUT","w",stdout);
  125.     }
  126.     cin >> t;
  127.     while (t--) {
  128.         cin >> n;
  129.  
  130.         for (int u=1;u<=n;u++) {
  131.             sz[u] = 0;
  132.             h[u] = 0;
  133.             pos[u] = 0;
  134.             head[u] = 0;
  135.             edges[u] = {0,0,0};
  136.             g[u].clear();
  137.         }
  138.         cur_p = 0;
  139.         for (int i=1;i< n*4;i++) {
  140.             st[i] = {-inf,inf,1};
  141.         }
  142.  
  143.         for (int i=1;i<n;i++) {
  144.             int u,v,w;
  145.             cin >> u >> v >> w;
  146.             edges[i] = {u,v,w};
  147.             g[u].push_back({v,w});
  148.             g[v].push_back({u,w});
  149.         }
  150.  
  151.         dfs(1,-1);
  152.         hld(1,1);
  153.         for (int u = 1;u<=n;u++) change(1,1,n,pos[u],val[u]);
  154.         while (1) {
  155.             string s;
  156.             cin >> s;
  157.             if (s == "DONE") break;
  158.             int a,b;
  159.             cin >> a >> b;
  160.             if (s[0] == 'Q') {
  161.                 if (a == b) {
  162.                     cout << "0\n";
  163.                     continue;
  164.                 }
  165.                 int lca = LCA(a,b);
  166.                 int ans = -inf;
  167.                 while (head[a] != head[lca]) {
  168.                     ans = max (ans, getmax(1,1,n,pos[a],pos[head[a]]).ma);
  169.                     a = par[0][head[a]];
  170.                 }
  171.                 while (head[b] != head[lca]) {
  172.                     ans = max (ans, getmax(1,1,n,pos[b],pos[head[b]]).ma);
  173.                     b = par[0][head[b]];
  174.                 }
  175.                 if (a != lca) ans = max (ans, getmax(1,1,n,pos[a],pos[lca] + 1).ma);
  176.                 if (b != lca) ans = max (ans, getmax(1,1,n,pos[b],pos[lca] + 1).ma);
  177.                 cout << ans << '\n';
  178.             }
  179.             if (s[0] == 'N') {
  180.                 int lca = LCA(a,b);
  181.                 while (head[a] != head[lca]) {
  182.                     neg(1,1,n,pos[a],pos[head[a]]);
  183.                     a = par[0][head[a]];
  184.                 }
  185.                 while (head[b] != head[lca]) {
  186.                     neg(1,1,n,pos[b],pos[head[b]]);
  187.                     b = par[0][head[b]];
  188.                 }
  189.                 if (a != lca) neg(1,1,n,pos[a],pos[lca] + 1);
  190.                 if (b != lca) neg(1,1,n,pos[b],pos[lca] + 1);
  191.             }
  192.             if (s[0] == 'C') {
  193.                 int u = edges[a].u, v = edges[a].v;
  194.                 if (u == par[0][v]) change(1,1,n,pos[v],b);
  195.                 else change(1,1,n,pos[u],b);
  196.             }
  197.         }
  198.     }
  199.     return 0;
  200. }
  201.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/4Kq9yr
language:
C++14 (clang 8.0)
created:
13 days 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!