… QTREE \u57fa\u7840\u4e0a\u589e\u52a0\u4e00\u4e2a\u53d6\u53cd\u64cd\u4f5c. <\/p>\n
… \u7565<\/p>\n
<\/p>\n
\r\n\/** ` Micro Mezzo Macro Flation -- Overheated Economy ., **\/\r\n\r\n#include <iostream>\r\n#include <cstring>\r\n#include <cstdio>\r\n#include <cmath>\r\n#include <vector>\r\n\r\nusing namespace std;\r\n\r\n#define REP(i, n) for (int i=0;i<int(n);++i)\r\n#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)\r\n#define REP_1(i, n) for (int i=1;i<=int(n);++i)\r\n#define FOR_C(i, a, b) for (int b____=int(b),i=a;i<b____;++i)\r\n#define DO(n) while(n--)\r\n#define SZ(A) int(A.size())\r\n#define PB push_back\r\n#define MP(A, B) make_pair(A, B)\r\n#define Rush int T____; RD(T____); DO(T____)\r\n#pragma comment(linker, "\/STACK:36777216")\r\n#pragma GCC optimize ("O2")\r\n\r\ntemplate<class T> inline void RD(T &);\r\ntemplate<class T> inline void OT(const T &);\r\ntemplate<class T> inline T& _RD(T &x){ RD(x); return x;}\r\ninline void RS(char *s){scanf("%s", s);}\r\ntemplate<class T0, class T1> inline void RD(T0 &x0, T1 &x1){RD(x0), RD(x1);}\r\ntemplate<class T0, class T1, class T2> inline void RD(T0 &x0, T1 &x1, T2 &x2){RD(x0), RD(x1), RD(x2);}\r\ntemplate<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}\r\ntemplate<class T0, class T1, class T2, class T3> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3){RST(A0), RST(A1), RST(A2), RST(A3);}\r\ntemplate<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}\r\ntemplate<class T> inline void CLR(T &A){A.clear();}\r\ntemplate<class T> inline void checkMax(T &a,const T b){if (b>a) a=b;}\r\ninline int _1(int i){return 1<<i;}\r\ntemplate<class T> inline void RD(T &x){\r\n \/\/ char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';\r\n scanf("%d", &x);\r\n }\r\ntemplate<class T> inline void OT(const T &x){printf("%d\\n", x);}\r\ntemplate<class T> inline T min(T a, T b, T c){return min(min(a, b), c);}\r\ntemplate<class T> inline T max(T a, T b, T c){return max(max(a, b), c);}\r\n\r\nconst int INF = 0x7fffffff;\r\n\/* .................................................................................................................................. *\/\r\n\r\nconst int N = 10001, M = 2 * N;\r\n\r\nint l[N], r[N], p[N], w0[N], w1[N] = {-INF}, w2[N] = {INF}, neg[N]; bool rt[N];\r\n\/\/ Link-cut tree\r\nint hd[N], nxt[M], a[M], b[M], w[M], h[M\/2];\r\n\/\/ Adjacent list\r\nint n, res;\r\n\r\n#define lx l[x]\r\n#define rx r[x]\r\n\r\n\r\ninline void Neg(int x){\r\n if (x == 0) return;\r\n w0[x] = -w0[x]; int t = w1[x]; w1[x] = -w2[x], w2[x] = -t, neg[x] ^= 1;\r\n}\r\n\r\ninline void Release(int x){\r\n if (x == 0 || !neg[x]) return;\r\n Neg(lx), Neg(rx), neg[x] = 0;\r\n}\r\n\r\ninline void Update(int x){\r\n w1[x] = max(w0[x], w1[lx], w1[rx]);\r\n w2[x] = min(w0[x], w2[lx], w2[rx]);\r\n}\r\n\r\ninline void Set(int l[], int y, int x){\r\n l[y] = x, p[x] = y;\r\n}\r\n\r\n#define z p[y]\r\ninline void Rotate(int x){\r\n int y = p[x];\r\n\r\n if (!rt[y]) Release(z), Set(y == l[z] ? l : r, z, x);\r\n else p[x] = z;\r\n\r\n Release(y), Release(x);\r\n\r\n if (x == l[y]) Set(l, y, rx), Set(r, x, y);\r\n else Set(r, y, lx), Set(l, x, y);\r\n\r\n if (rt[y]) rt[y] = false, rt[x] = true;\r\n Update(y);\r\n}\r\n\r\ninline void Splay(int x){\r\n while (!rt[x]) Rotate(x);\r\n}\r\n\r\nvoid Access(int x){\r\n int y = 0; do{\r\n Splay(x), Release(x);\r\n rt[rx] = true, rt[rx = y] = false, Update(x);\r\n x = p[y = x];\r\n } while (x);\r\n}\r\n\r\n#define v b[i]\r\n#define w w[i]\r\n\r\ninline void dfs(int u = 1){\r\n for(int i=hd[u];i;i=nxt[i]) if (!p[v]){\r\n p[v] = u, w0[v] = w, dfs(h[i>>1] = v);\r\n }\r\n}\r\n\r\n#undef x\r\n#undef w\r\n\r\nvoid Query(int x, int y){\r\n Access(y); y = 0; do{\r\n Splay(x), Release(x);if (!p[x]) res = max(w1[rx], w1[y]);\r\n rt[rx] = true, rt[rx = y] = false, Update(x);\r\n x = p[y = x];\r\n } while (x);\r\n}\r\n\r\nvoid Modify(int x, int val){\r\n \/\/Access(x),\r\n Splay(x), w0[x] = val;\r\n \/\/ Update(x);\r\n}\r\n\r\nvoid Negate(int x, int y){\r\n Access(y); y = 0; do{\r\n Splay(x), Release(x); if (!p[x]) Neg(rx), Neg(y);\r\n rt[rx] = true, rt[rx = y] = false, Update(x);\r\n x = p[y = x];\r\n } while (x);\r\n}\r\n\r\nint main(){\r\n\r\n \/\/freopen("in.txt", "r", stdin);\r\n \/\/freopen("out.txt", "w", stdout);\r\n \/\/ios::sync_with_stdio(false);\r\n\r\n Rush{\r\n \/\/ Initializing Phase ...\r\n\r\n FOR_C(i, 2, _RD(n) << 1){\r\n RD(a[i], b[i], w[i]), a[i|1] = b[i], b[i|1] = a[i], w[i|1] = w[i];\r\n nxt[i] = hd[a[i]], hd[a[i]] = i; ++i;\r\n nxt[i] = hd[a[i]], hd[a[i]] = i;\r\n }\r\n\r\n FLC(rt, true), p[1] = -1, dfs(), p[1] = 0;\r\n\r\n \/\/ Interaction Phase ...\r\n\r\n int a, b; char cmd[5];\r\n\r\n while (true){\r\n RS(cmd); if (cmd[0] == 'Q') RD(a, b), Query(a, b), OT(res);\r\n else if (cmd[0] == 'C') RD(a, b), Modify(h[a], b);\r\n else if (cmd[0] == 'N') RD(a, b), Negate(a, b);\r\n else break;\r\n }\r\n\r\n \/\/ Rececling ....\r\n\r\n RST(hd, p, l, r);\r\n }\r\n}\r\n\r\n<\/pre>\nExternal link :<\/h3>\n