… \u52a8\u6001\u7ef4\u62a4\u4e00\u7ec4\u68ee\u6797\uff0c\u8981\u6c42\u652f\u6301\u4ee5\u4e0b\u64cd\u4f5c\uff1a<\/p>\n
<\/p>\n
\u3002\u3002Link-Cut Tree \u7684\u6838\u5fc3\u64cd\u4f5c \u3002\u3002Access()\u3002\u3002\uff08\u53ea\u6709\u8c03\u7528\u8fd9\u4e2a\u8fc7\u7a0b\u4f1a\u6539\u53d8\u8fb9\u7684\u865a\u5b9e\u5173\u7cfb \uff08Solid \/ Dashed\uff09 \uff09\u3002\u3002 \u3002\u518d\u4ee5\u6b64\u9898\u4e3a\u4f8b\u3002\u3002<\/p>\n \u5bf9\u4e8e\u5f97\u5230\u4e00\u6761\u8def\u5f84\u7684\u505a\u6cd5\uff0c\u5148 \u4e00\u4e2a Access() \u8fc7\u7a0b\u8bbf\u95ee\u5176\u4e2d\u7684\u4e00\u4e2a\u70b9\uff0c\u518d\u901a\u8fc7 \u4e00\u4e2a\u4fee\u6539\u7684 Access() \u8fc7\u7a0b \u8bbf\u95ee\u53e6\u4e00\u4e2a\u70b9\uff0c \u7136\u540e\u4f7f\u7528 .. max(w1[rx], w0[x], w1[y]) .. \u5c31\u53ef\u4ee5\u5f97\u5230\u8fd9\u6761\u8def\u5f84\u4e0a\u70b9\u6743\u7684\u6700\u5927\u503c\u3002\uff08\u5982\u679c\u662f\u8fb9\u6743\u7cfb\u5217\u95ee\u9898<\/a>\uff0c\u4e2d\u95f4\u7684 w0[x] \u4f1a\u6d88\u5931\u3002\u3002\u3002\u3002 \uff09<\/p>\n \u5bf9\u4e8e\u4fee\u6539\u64cd\u4f5c\uff0c\u6211\u4eec\u9700\u8981\u518d\u5f15\u5165\u4e00\u4e2a delay \u6807\u8bb0\u3002<\/p>\n \u4e8e\u662f\u5f97\u5230 Modify() \u7684\u8fc7\u7a0b\u3002\u3002\u3002<\/p>\n \u3002\u3002\u5404\u79cd\u7ef4\u62a4\u5c31\u53ef\u4ee5\u4e86\u3002\u3002\u3002\u3002<\/p>\n ( .. HDOJ Rank I . 593ms \u8fbe\u6210 .. \uff09<\/p>\n Link-Cut Tree \u7684\u5148\u4fee\u6280\u80fd\u662f Splay\uff0c\u63a8\u8350\u5165\u95e8\u9898\u3002\u3002 \u4e4b\u540e\u505a\u8fd9\u9898\u4e4b\u524d\u4e00\u5b9a\u8981\u6709\u540c\u65f6\u7ef4\u62a4\u5411\u4e0a\u5411\u4e0b\u4f20\u9012\u7684\u7ecf\u9a8c\u3002 \u53ef\u4ee5\u53c2\u89c1\u90a3\u4e24\u9053 S \u7ea7\u6570\u636e\u7ed3\u6784 .. . \u989d\u3002\u3002\u3002\u8865\u5145\u4e00\u4e9b\u95ee\u9898\uff0c \uff08\u989d\uff0c\u6700\u540e\u8bf4\u4e00\u4e0b\u7531\u4e8e\u6211\u4e00\u76f4\u4f7f\u7528\u5355\u65cb Splay\u3002\u3002 Splay() \u8fc7\u7a0b\u88ab\u5199\u7684\u53ea\u6709\u4e00\u884c\u3002\u3002\u6ca1\u6709\u5bf9\u65cb\u8f6c\u65b9\u5411\u7684\u5224\u65ad\u6240\u4ee5\u662f\u9700\u8981\u5199\u4e00\u90e8\u5206\u6807\u8bb0\u4e0b\u653e\u5230 Rotate() \u91cc\u9762\u7684\u3002\u3002\uff09 \u5982\u679c\u4f60\u662f\u300c\u6570\u636e\u7ed3\u6784\u63a7\u300d\u3002\u3002\u5bf9\u8fd9\u51e0\u4e2a\u975e\u5e38\u611f\u5174\u8da3\uff0c\u6211\u731c\u4f60\u53ef\u80fd\u4f1a\u559c\u6b22\u8fd9\u4e2a\u3002\u3002.[\u6316\u5751]\u52a8\u6001\u6811\u4e0e\u6811\u94fe\u5256\u5206.. .<\/a>
\n\u3002\u3002\u4ecb\u4e8e Splay \u4fdd\u5b58\u8def\u5f84\u7684\u7279\u6b8a\u65b9\u5f0f\uff0c\u901a\u5e38\u3002\u3002\u8981\u5c06\u9700\u8981\u64cd\u4f5c\u7684\u8282\u70b9 Splay() \u5230\u6839\uff08\u4ee5\u83b7\u5f97\u5176\u5bf9\u6574\u68f5\u5b50\u6811\u7684\u5b8c\u6574\u4fe1\u606f\uff09\u4e4b\u540e\u624d\u53ef\u4ee5\u5bf9\u5176\u8fdb\u884c\u8fdb\u4e00\u6b65\u7684\u64cd\u4f5c .. .
\n\u8fd9\u91cc\u9700\u8981\u5f15\u5165 rev \u6807\u8bb0\u8fdb\u884c\u4fee\u6539\u6811\u6839\u7684\u64cd\u4f5c\uff08\u53ea\u5b58\u5728\u4e8e\u4f5c\u7528\u4e8e\u65e0\u6839\u6811\u7684\u9898\u76ee\u4e2d\uff0c\u4f8b\u5982 SPOJ 4155. OTOCI<\/a> …\uff09<\/p>\n\r\nvoid Link(int x, int y){\r\n if (Root(x) == Root(y)){\r\n puts("-1");\r\n }\r\n else {\r\n Evert(x), Splay(x), p[x] = y, Access(x);\r\n }\r\n}\r\n \r\nvoid Cut(int y, int x){\r\n if (x == y || Root(x) != Root(y)){\r\n puts("-1");\r\n }\r\n else {\r\n Evert(y), Splay(y), Access(x), Splay(x);\r\n p[lx] = p[x], rt[lx] = true, p[x] = lx = 0;\r\n \/\/Update(x);\r\n }\r\n}\r\n<\/pre>\n
\n\u5728\u7b2c\u4e8c\u6b21 Access() \u7684\u6700\u540e\u9636\u6bb5\u4f1a\u901a\u8fc7 p[] \u6307\u9488\u5f97\u5230\u8fd9\u4e24\u70b9\u4e4b\u95f4\u7684 LCA … \uff08Orz\uff09
\n\uff08\u3002\u3002\u4ea4\u6362 Access() \u7684\u987a\u5e8f\u4e0d\u5f71\u54cd\u3002\u3002\uff09<\/p>\n\r\nvoid Query(int x, int y){\r\n if (Root(x) != Root(y)){\r\n puts("-1");\r\n }\r\n else {\r\n Access(y); y = 0; do{\r\n Splay(x), Release(x); if (!p[x]) OT(max(w1[rx], w0[x], 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\n<\/pre>\n\r\ninline void Inc(int x, int d){\r\n if (x == 0) return;\r\n\r\n w0[x] += d, w1[x] += d, delay[x] += d;\r\n}\r\n<\/pre>\n\r\nvoid Modify(int x, int y, int w){\r\n if (Root(x) != Root(y)){\r\n puts("-1");\r\n }\r\n else {\r\n Access(y); y = 0; do{\r\n Splay(x), Release(x); if (!p[x]) Inc(rx, w), w0[x] += w, Inc(y, w);\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<\/pre>\nFurther discussion :<\/h3>\n
\nSGU 187. Twist and whirl — want to cheat .. . <\/a><\/p>\n
\n\uff08\u81ea\u9876\u5411\u4e0b\u4e0b\u653e (Release()) \u7684\u6807\u8bb0 (rev, delay)\uff0c\u548c\u81ea\u5e95\u5411\u4e0a\u7ef4\u62a4 (Update()) \u7684\u5173\u952e\u5b57 (w0, w1)\uff09\u3002\u3002<\/p>\n
\nNOI 2005. \u7ef4\u4fee\u6570\u5217<\/a> \u3002\u3002\u548c\u3002\u3002
\nSPOJ 1557. Can you answer these queries II<\/a>\u3002\u3002<\/p>\n
\n\u9996\u5148\uff0c\u5404\u4e2a\u5b50\u8fc7\u7a0b\u9700\u8981\u505a\u5230 \u2014\u2014\u2014\u2014 \u5404\u53f8\u5176\u804c\u3002\u3002
\n\u8fd9\u91cc\u7684\u542b\u4e49\u662f\u5c3d\u91cf\u4e0d\u8981\u505a\u989d\u5916\u300c\u753b\u86c7\u6dfb\u8db3\u300d\u7684\u4e8b\u60c5\uff0c\u4f8b\u5982 \u3002\u3002<\/p>\n\n
Access() \u64cd\u4f5c\u4e4b\u540e\u7d27\u63a5\u7740 Splay() \u5230\u6839\u8282\u70b9 \uff08\u76f4\u63a5\u56fa\u5316\u5728 Access() \u91cc\u9762\uff09\u3002\u3002\u3002<\/del>\u3002\u3002 \u4e0d\u5fc5\u8981\u3002\u3002\u3002\u4f60\u53ef\u4ee5\u901a\u8fc7 \u8c03\u7528 _Access(x) \uff08\u52a0\u524d\u7f00\u4e0b\u5212\u7ebf\u8868\u793a\u4e00\u4e2a\u8fd4\u56de\u7248\u672c\u3002\u3002\uff09\u7ed3\u675f\u7136\u540e\u8fd4\u56de\u5176\u6700\u540e\u8bbf\u95ee\u5230\u7684\u7ed3\u70b9\uff08\u4e5f\u5c31\u662f\u6b64\u65f6\u7684\u6811\u6839\u3002\uff09\u3002\u3002\u5bf9\u8fd9\u4e2a\u7ed3\u70b9\u8fdb\u884c\u64cd\u4f5c\u5373\u53ef\u3002\u3002<\/li>\nUpdate() \u8fc7\u7a0b\u91cc\u9762\u5d4c\u4e00\u4e2a Release() \u3002\u3002\u3002<\/del>\uff08\u8fd9\u4e2a\u3002\u3002\u56e0\u4e3a\u6b64\u9898\u4e2d\u7ef4\u62a4\u7684 w1 \u4fe1\u606f\uff0c\u5de6\u53f3\u5b50\u6811\u662f\u5426\u4ea4\u6362\u5bf9\u5176\u4e0d\u9020\u6210\u5f71\u54cd\u3002\u3002\u663e\u7136\u53ef\u4ee5\u53bb\u6389\u3002\u3002( GSS 6<\/a> )\u3002\u3002\uff09<\/li>\nRotate() \u64cd\u4f5c\u91cc\u9762\u4e0d\u505c\u7684 Update(), Release(), Update(), Release() \u3002\u3002.. .<\/del><\/li>\n
\n\uff08\u3002\u3002Unsolved Problem .. \u3002\u3002\uff09<\/p>\n
\n\u6211\u6536\u96c6\u4e86\u4e00\u4e9b\u8d44\u6e90 (Resource) \u548c\u4e60\u9898 (Exercise)<\/p>\n\r\n#include <iostream>\r\n#include <cstring>\r\n#include <cstdio>\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=int(a);i<b____;++i)\r\n#define REP_1_C(i, n) for (int n____=int(n),i=1;i<=n____;++i)\r\n#define DO(n) while(n--)\r\n#define DO_C(n) int n____ = n; while(n____--)\r\n\r\ntemplate<class T> inline void RD(T &x){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\ninline int RD(){ int x; RD(x); return x;}\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 OT(const T &x){printf("%d\\n", x);}\r\ntemplate<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}\r\ntemplate<class T0, class T1, class T2, class T3, class T4, class T5> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);}\r\ntemplate<class T> inline T max(T a, T b, T c){return max(max(a, b), c);}\r\n\r\n\/*--------*\/\r\n\r\nconst int N = 300009, M = 2 * N;\r\n\r\nint l[N], r[N], p[N], w0[N], w1[N], delay[N], rev[N]; bool rt[N];\r\n\/\/ Link-cut tree\r\nint hd[N], nxt[M], a[M], b[M];\r\n\/\/ Adjacent list\r\nint n;\r\n\r\n#define lx l[x]\r\n#define rx r[x]\r\n\r\n\/\/ private:\r\n\r\ninline void Inc(int x, int d){\r\n if (x == 0) return;\r\n w0[x] += d, w1[x] += d, delay[x] += d;\r\n}\r\n\r\ninline void Release(int x){\r\n if (x == 0) return;\r\n\r\n if (rev[x]){\r\n swap(lx, rx);\r\n rev[lx] ^=1, rev[rx] ^=1;\r\n rev[x] = 0;\r\n }\r\n\r\n if (delay[x]){\r\n Inc(lx, delay[x]), Inc(rx, delay[x]);\r\n delay[x] = 0;\r\n }\r\n}\r\n\r\ninline void Update(int x){\r\n w1[x] = max(w0[x], w1[lx], w1[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\ninline int 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 return y;\r\n}\r\n\r\ninline int Root(int x){\r\n for (x = Access(x); Release(x), lx; x = lx);\r\n return x;\r\n}\r\n\r\ninline void Evert(int x){\r\n rev[Access(x)] ^= 1;\r\n}\r\n\r\n\/\/ public:\r\n\r\nvoid Query(int x, int y){\r\n if (Root(x) != Root(y))\r\n puts("-1");\r\n else {\r\n Access(y); y = 0; do{\r\n Splay(x), Release(x); if (!p[x]) OT(max(w1[rx], w0[x], 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\n\r\nvoid Link(int x, int y){\r\n if (Root(x) == Root(y))\r\n puts("-1");\r\n else {\r\n Evert(x), Splay(x), p[x] = y, Access(x);\r\n }\r\n}\r\n\r\n\/\/ Set y as a root, Cut the connection between x and p[x] ..\r\nvoid Cut(int y, int x){\r\n if (x == y || Root(x) != Root(y))\r\n puts("-1");\r\n else {\r\n Evert(y), Splay(y), Access(x), Splay(x);\r\n p[lx] = p[x], rt[lx] = true, p[x] = lx = 0;\r\n }\r\n}\r\n\r\nvoid Modify(int x, int y, int w){\r\n if (Root(x) != Root(y))\r\n puts("-1");\r\n else {\r\n Access(y); y = 0; do{\r\n Splay(x), Release(x); if (!p[x]) Inc(rx, w), w0[x] += w, Inc(y, w);\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\r\n#define v b[i]\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, dfs(v);\r\n }\r\n}\r\n\r\nint main(){\r\n \/\/freopen("in.txt", "r", stdin);\r\n \/\/freopen("out.txt", "w", stdout);\r\n\r\n while (scanf("%d", &n) != EOF){\r\n \/\/ Initializing Phase\r\n FOR_C(i, 2, n << 1){\r\n RD(a[i], b[i]), a[i|1] = b[i], b[i|1] = a[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 REP_1(i, n) RD(w0[i]), rt[i] = true;\r\n p[1] = -1, dfs(), p[1] = 0;\r\n\r\n \/\/Interaction Phase\r\n int a, b, cmd; DO_C(RD()){\r\n RD(cmd, a, b); if (cmd == 1) Link(a, b);\r\n else if (cmd == 2) Cut(a, b);\r\n else if (cmd == 3) Modify(b, RD(), a);\r\n else Query(a, b);\r\n }\r\n\r\n puts("");\r\n\r\n \/\/ Rececling ...\r\n RST(hd, p, l, r, delay, rev);\r\n }\r\n}\r\n\r\n<\/pre>\n
\n\uff08
\n\u4e0b\u4e00\u9636\u6bb5\u7684\u4efb\u52a1\u3002\u3002\u6211\u89c9\u5f97\u52a8\u6001\u6811\u6211\u8fd8\u6ca1\u5f04\u660e\u767d\u3002\u3002\u8fd8\u60f3\u5728\u82b1\u4e00\u6bb5\u65f6\u95f4\u3002\u3002
\n\u5148\u6253\u7b97\u5148\u5199\u4e00\u4e0b\u52a8\u6001\u6811\u7684\u90a3\u4e2a\u300c\u6b63\u5f53\u7528\u9014\u300d \u2014\u2014\u2014\u2014 \u4f18\u5316\u7f51\u7edc\u6d41\u3002\u3002
\n\u4e4b\u540e\u3002\u3002
\n\u6211\u5c31\u53bb\u89e3\u51b3\u6389 fhq \u7684 1<\/a>\u30012<\/a>\u30013<\/a> \u3002\u3002\u4e09\u4e2a\u96be\u9898\u3002\u3002(> <)\u3002\u3002\u3002\u3002\n\uff09\n\n\n--- UPD ---\n\u73b0\u5728\u7684\u641e\u6cd5\u3002<\/a><\/p>\nExternal link :<\/h3>\n