fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. //  M1nK's Ducky Mask: "Strongest Man In The World"
  4.  
  5. //#pragma GCC target ("avx2")
  6. //#pragma GCC optimization ("O3")
  7. //#pragma GCC optimization ("unroll-loops")
  8.  
  9. #define task "TASK"
  10.  
  11. #define fi first
  12. #define se second
  13. #define pi acos (-1)
  14. #define pb push_back
  15. #define ll long long
  16. #define ld long double
  17. #define pll pair <ll, ll>
  18. #define pll2 pair <ll, pll>
  19. #define all(a) a.begin (), a.end ()
  20. #define heap_max(a) priority_queue <a>
  21. #define FOR(i, a, b) for (ll i = (a); i <= (b); ++i)
  22. #define FOD(i, a, b) for (ll i = (a); i >= (b); --i)
  23. #define FOr(i, a, b, c) for (ll i = (a); i <= (b); i += (c))
  24. #define FOd(i, a, b, c) for (ll i = (a); i >= (b); i -= (c))
  25. #define heap_min(a) priority_queue <a, vector <a>, greater <a>>
  26.  
  27. #define Mirai ios_base:: sync_with_stdio (0);
  28. #define Kuriyama cin.tie (nullptr); cout.tie (nullptr);
  29.  
  30. using namespace std;
  31. const ll INF = 1e18;
  32. const ll MOD = 1e9 + 7;
  33. const ll minN = 1e3 + 7;
  34. const ll maxN = 1e4 + 7;
  35. const ll LOG = __lg (maxN) + 1; 
  36.  
  37. template <class X> ll getbit (X s, ll i) { return (s >> i) & 1; }
  38. template <class X> ll cntbit (X s) { return __builtin_popcountll (s); }
  39. template <class X, class Y> bool maximize (X &a, Y b) { if (a < b) return a = b, 1; return 0; }
  40. template <class X, class Y> bool minimize (X &a, Y b) { if (a > b) return a = b, 1; return 0; }
  41.  
  42. // --------------- M1nK_08 --------------- //
  43.  
  44. string type;
  45. ll t, n, u, v, w;
  46.  
  47. vector <ll> adj[maxN];
  48. ll a[maxN], val[maxN], edge[maxN];
  49.  
  50. struct Data { ll x, y, z; } p[maxN];
  51.  
  52.  
  53. ll sz[maxN], par[maxN], h[maxN], hv[maxN];
  54. void DFS (ll u, ll p) {
  55.     sz[u] = 1;
  56.     for (auto v: adj[u]) {
  57.         if (v == p) continue;
  58.         par[v] = u;
  59.         h[v] = h[u] + 1;
  60.         DFS (v, u);
  61.         sz[u] += sz[v];
  62.         if (sz[v] > sz[hv[u]]) hv[u] = v;
  63.     }
  64. }
  65.  
  66. ll st[4 * maxN][2], lz[4 * maxN];
  67. void Lazy (ll id) {
  68.     lz[id] ^= 1;
  69.     ll tmp = st[id][1];
  70.     st[id][1] = -st[id][0];
  71.     st[id][0] = -tmp;
  72. }
  73. void Down (ll id) {
  74.     if (lz[id]) {
  75.         Lazy (id << 1);
  76.         Lazy (id << 1 | 1);
  77.         lz[id] = 0;
  78.     }
  79. }
  80. void Build (ll id, ll l, ll r) {
  81.     if (l == r) {
  82.         st[id][0] = st[id][1] = a[l];
  83.         return;
  84.     }
  85.     ll mid = (l + r) >> 1;
  86.     Build (id << 1, l, mid);
  87.     Build (id << 1 | 1, mid + 1, r);
  88.     st[id][0] = min (st[id << 1][0], st[id << 1 | 1][0]);
  89.     st[id][1] = max (st[id << 1][1], st[id << 1 | 1][1]);
  90. }
  91. void Upd (ll id, ll l, ll r, ll pos, ll val) {
  92.     if (l == r) {
  93.         st[id][0] = st[id][1] = val;
  94.         return;
  95.     }
  96.     Down (id);
  97.     ll mid = (l + r) >> 1;
  98.     if (pos <= mid) Upd (id << 1, l, mid, pos, val);
  99.     else Upd (id << 1 | 1, mid + 1, r, pos, val);
  100.     st[id][0] = min (st[id << 1][0], st[id << 1 | 1][0]);
  101.     st[id][1] = max (st[id << 1][1], st[id << 1 | 1][1]);
  102. }
  103. ll Get (ll id, ll l, ll r, ll u, ll v) {
  104.     if (r < u || v < l) return -INF;
  105.     if (u <= l && r <= v) return st[id][1];
  106.     Down (id);
  107.     ll mid = (l + r) >> 1;
  108.     return max (Get (id << 1, l, mid, u, v), Get (id << 1 | 1, mid + 1, r, u, v));
  109. }
  110. void Neg (ll id, ll l, ll r, ll u, ll v) {
  111.     if (r < u || v < l) return;
  112.     if (u <= l && r <= v) {
  113.         Lazy (id);
  114.         return;
  115.     }
  116.     Down (id);
  117.     ll mid = (l + r) >> 1;
  118.     Neg (id << 1, l, mid, u, v);
  119.     Neg (id << 1 | 1, mid + 1, r, u, v);
  120.     st[id][0] = min (st[id << 1][0], st[id << 1 | 1][0]);
  121.     st[id][1] = max (st[id << 1][1], st[id << 1 | 1][1]);
  122. }
  123.  
  124. ll curpos = 1;
  125. ll ID[maxN], pos[maxN];
  126. void HLD (ll u, ll v) {
  127.     ID[u] = v;
  128.     pos[u] = curpos++;
  129.     if (!!hv[u]) HLD (hv[u], v);
  130.     for (auto v: adj[u]) if (v != par[u] && v != hv[u]) HLD (v, v);
  131. }
  132. void UpdPath (ll u, ll v) {
  133.     while (ID[u] != ID[v]) {
  134.         if (h[ID[u]] < h[ID[v]]) swap (u, v);
  135.         Neg (1, 1, n, pos[ID[u]], pos[u]);
  136.         u = par[ID[u]];
  137.     }
  138.     Neg (1, 1, n, min (pos[u], pos[v]) + 1, max (pos[u], pos[v]));
  139. }
  140. ll Query (ll u, ll v) {
  141.     ll ans = -INF;
  142.     while (ID[u] != ID[v]) {
  143.         if (h[ID[u]] < h[ID[v]]) swap (u, v);
  144.         maximize (ans, Get (1, 1, n, pos[ID[u]], pos[u]));
  145.         u = par[ID[u]];
  146.     }
  147.     return max (ans, Get (1, 1, n, min (pos[u], pos[v]) + 1, max (pos[u], pos[v])));
  148. }
  149.  
  150. void Clear () {
  151.     curpos = 1;
  152.     FOR (i, 1, n) {
  153.         adj[i].clear ();
  154.         p[i] = {0, 0, 0};
  155.         a[i] = val[i] = edge[i] = sz[i] = par[i] = h[i] = hv[i] = ID[i] = pos[i] = 0;
  156.     }
  157.     FOR (id, 0, 4 * maxN) st[id][0] = st[id][1] = lz[id] = 0;
  158. }
  159.  
  160. void Solve () {
  161.     cin >> t;
  162.     while (t--) {
  163.         cin >> n;
  164.         Clear ();
  165.         FOR (i, 2, n) {
  166.             cin >> u >> v >> w;
  167.             adj[u].pb (v);
  168.             adj[v].pb (u);
  169.             p[i] = {u, v, w};
  170.         }
  171.         DFS (1, -1);
  172.         HLD (1, 1);
  173.         FOR (i, 2, n) {
  174.             u = p[i].x;
  175.             v = p[i].y;
  176.             w = p[i].z;
  177.             if (u == par[v]) edge[i - 1] = v, val[v] = w;
  178.             else edge[i - 1] = u, val[u] = w;
  179.         }
  180.         FOR (i, 1, n) a[pos[i]] = val[i];
  181.         Build (1, 1, n);
  182.         while (cin >> type) {
  183.             if (type == "DONE") break;
  184.             cin >> u >> v;
  185.             if (type == "CHANGE") Upd (1, 1, n, pos[edge[u]], v);
  186.             if (type == "NEGATE") UpdPath (u, v);
  187.             if (type == "QUERY") cout << (u == v ? 0 : Query (u, v)) << '\n';
  188.         }
  189.     }
  190. }
  191.  
  192. signed main (void) {
  193.     Mirai Kuriyama;
  194.     if (fopen (task".INP", "r")) {
  195.         freopen (task".INP", "r", stdin);
  196.         freopen (task".OUT", "w", stdout);
  197.     } 
  198.     Solve ();
  199.     return 0;
  200. }
  201.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
stdout 
1
3
https://ideone.com/N7cJS8
language:
C++14 (gcc 8.3)
created:
188 days ago
visibility:
secret

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!