Brief description :
… 动态维护一组森林，要求支持以下操作：
- Link(a, b) 如果 a，b 不在同一颗子树中，则通过在 a，b 之间连边的方式，连接这两棵子树。
- Cut(a, b) 如果 a，b 在同一颗子树中、且 a != b，则将 a 视为这棵子树的根之后，切断 b 与其父亲结点的连接。
- Modify(w, a, b) 如果 a, b 在同一颗子树中，则将 a, b 之间路径上所有的点权增加 w。
- Query(a, b) 如果 a, b 在同一颗子树中，返回 a, b 之间路径上点权的最大值。
Analysis :
。。Link-Cut Tree 的核心操作 。。Access()。。（只有调用这个过程会改变边的虚实关系 （Solid / Dashed） ）。。
。。介于 Splay 保存路径的特殊方式，通常。。要将需要操作的节点 Splay() 到根（以获得其对整棵子树的完整信息）之后才可以对其进行进一步的操作 .. .
这里需要引入 rev 标记进行修改树根的操作（只存在于作用于无根树的题目中，例如 SPOJ 4155. OTOCI …）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | void Link(int x, int y){ if (Root(x) == Root(y)){ puts("-1"); } else { Evert(x), Splay(x), p[x] = y, Access(x); }} void Cut(int y, int x){ if (x == y || Root(x) != Root(y)){ puts("-1"); } else { Evert(y), Splay(y), Access(x), Splay(x); p[lx] = p[x], rt[lx] = true, p[x] = lx = 0; //Update(x); }} |
。再以此题为例。。
对于得到一条路径的做法，先 一个 Access() 过程访问其中的一个点，再通过 一个修改的 Access() 过程 访问另一个点，
在第二次 Access() 的最后阶段会通过 p[] 指针得到这两点之间的 LCA … （Orz）
（。。交换 Access() 的顺序不影响。。）
然后使用 .. max(w1[rx], w0[x], w1[y]) .. 就可以得到这条路径上点权的最大值。（如果是边权系列问题，中间的 w0[x] 会消失。。。。 ）
1 2 3 4 5 6 7 8 9 10 11 12 | void Query(int x, int y){ if (Root(x) != Root(y)){ puts("-1"); } else { Access(y); y = 0; do{ Splay(x), Release(x); if (!p[x]) OT(max(w1[rx], w0[x], w1[y])); rt[rx] = true, rt[rx = y] = false, Update(x); x = p[y = x]; } while (x); }} |
对于修改操作，我们需要再引入一个 delay 标记。
1 2 3 4 5 | inline void Inc(int x, int d){ if (x == 0) return; w0[x] += d, w1[x] += d, delay[x] += d;} |
于是得到 Modify() 的过程。。。
1 2 3 4 5 6 7 8 9 10 11 12 | void Modify(int x, int y, int w){ if (Root(x) != Root(y)){ puts("-1"); } else { Access(y); y = 0; do{ Splay(x), Release(x); if (!p[x]) Inc(rx, w), w0[x] += w, Inc(y, w); rt[rx] = true, rt[rx = y] = false, Update(x); x = p[y = x]; } while (x); }} |
。。各种维护就可以了。。。。
( .. HDOJ Rank I . 593ms 达成 .. ）
Further discussion :
Link-Cut Tree 的先修技能是 Splay，推荐入门题。。
SGU 187. Twist and whirl — want to cheat .. .
之后做这题之前一定要有同时维护向上向下传递的经验。
（自顶向下下放 (Release()) 的标记 (rev, delay)，和自底向上维护 (Update()) 的关键字 (w0, w1)）。。
可以参见那两道 S 级数据结构 .. .
NOI 2005. 维修数列 。。和。。
SPOJ 1557. Can you answer these queries II。。
额。。。补充一些问题，
首先，各个子过程需要做到 ———— 各司其职。。
这里的含义是尽量不要做额外「画蛇添足」的事情，例如 。。
Access() 操作之后紧接着 Splay() 到根节点 （直接固化在 Access() 里面）。。。。。 不必要。。。你可以通过 调用 _Access(x) （加前缀下划线表示一个返回版本。。）结束然后返回其最后访问到的结点（也就是此时的树根。）。。对这个结点进行操作即可。。Update() 过程里面嵌一个 Release() 。。。（这个。。因为此题中维护的 w1 信息，左右子树是否交换对其不造成影响。。显然可以去掉。。( GSS 6 )。。）Rotate() 操作里面不停的 Update(), Release(), Update(), Release() 。。.. .- …
- .
（额，最后说一下由于我一直使用单旋 Splay。。 Splay() 过程被写的只有一行。。没有对旋转方向的判断所以是需要写一部分标记下放到 Rotate() 里面的。。）
（。。Unsolved Problem .. 。。）
如果你是「数据结构控」。。对这几个非常感兴趣，我猜你可能会喜欢这个。。.[挖坑]动态树与树链剖分.. .
我收集了一些资源 (Resource) 和习题 (Exercise)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 | #include <iostream>#include <cstring>#include <cstdio>using namespace std;#define REP(i, n) for (int i=0;i<int(n);++i)#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)#define REP_1(i, n) for (int i=1;i<=int(n);++i)#define FOR_C(i, a, b) for (int b____=int(b),i=int(a);i<b____;++i)#define REP_1_C(i, n) for (int n____=int(n),i=1;i<=n____;++i)#define DO(n) while(n--)#define DO_C(n) int n____ = n; while(n____--)template<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';}inline int RD(){ int x; RD(x); return x;}template<class T0, class T1> inline void RD(T0 &x0, T1 &x1){RD(x0), RD(x1);}template<class T0, class T1, class T2> inline void RD(T0 &x0, T1 &x1, T2 &x2){RD(x0), RD(x1), RD(x2);}template<class T> inline void OT(const T &x){printf("%d\n", x);}template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}template<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);}template<class T> inline T max(T a, T b, T c){return max(max(a, b), c);}/*--------*/const int N = 300009, M = 2 * N;int l[N], r[N], p[N], w0[N], w1[N], delay[N], rev[N]; bool rt[N];// Link-cut treeint hd[N], nxt[M], a[M], b[M];// Adjacent listint n;#define lx l[x]#define rx r[x]// private:inline void Inc(int x, int d){ if (x == 0) return; w0[x] += d, w1[x] += d, delay[x] += d;}inline void Release(int x){ if (x == 0) return; if (rev[x]){ swap(lx, rx); rev[lx] ^=1, rev[rx] ^=1; rev[x] = 0; } if (delay[x]){ Inc(lx, delay[x]), Inc(rx, delay[x]); delay[x] = 0; }}inline void Update(int x){ w1[x] = max(w0[x], w1[lx], w1[rx]);}inline void Set(int l[], int y, int x){ l[y] = x, p[x] = y;}#define z p[y]inline void Rotate(int x){ int y = p[x]; if (!rt[y]) Release(z), Set(y == l[z] ? l : r, z, x); else p[x] = z; Release(y), Release(x); if (x == l[y]) Set(l, y, rx), Set(r, x, y); else Set(r, y, lx), Set(l, x, y); if (rt[y]) rt[y] = false, rt[x] = true; Update(y);}inline void Splay(int x){ while (!rt[x]) Rotate(x);}inline int Access(int x){ int y = 0; do{ Splay(x), Release(x); rt[rx] = true, rt[rx = y] = false, Update(x); x = p[y = x]; } while (x); return y;}inline int Root(int x){ for (x = Access(x); Release(x), lx; x = lx); return x;}inline void Evert(int x){ rev[Access(x)] ^= 1;}// public:void Query(int x, int y){ if (Root(x) != Root(y)) puts("-1"); else { Access(y); y = 0; do{ Splay(x), Release(x); if (!p[x]) OT(max(w1[rx], w0[x], w1[y])); rt[rx] = true, rt[rx = y] = false, Update(x); x = p[y = x]; } while (x); }}void Link(int x, int y){ if (Root(x) == Root(y)) puts("-1"); else { Evert(x), Splay(x), p[x] = y, Access(x); }}// Set y as a root, Cut the connection between x and p[x] ..void Cut(int y, int x){ if (x == y || Root(x) != Root(y)) puts("-1"); else { Evert(y), Splay(y), Access(x), Splay(x); p[lx] = p[x], rt[lx] = true, p[x] = lx = 0; }}void Modify(int x, int y, int w){ if (Root(x) != Root(y)) puts("-1"); else { Access(y); y = 0; do{ Splay(x), Release(x); if (!p[x]) Inc(rx, w), w0[x] += w, Inc(y, w); rt[rx] = true, rt[rx = y] = false, Update(x); x = p[y = x]; } while (x); }}#define v b[i]inline void dfs(int u = 1){ for(int i=hd[u];i;i=nxt[i]) if (!p[v]){ p[v] = u, dfs(v); }}int main(){ //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); while (scanf("%d", &n) != EOF){ // Initializing Phase FOR_C(i, 2, n << 1){ RD(a[i], b[i]), a[i|1] = b[i], b[i|1] = a[i]; nxt[i] = hd[a[i]], hd[a[i]] = i; ++i; nxt[i] = hd[a[i]], hd[a[i]] = i; } REP_1(i, n) RD(w0[i]), rt[i] = true; p[1] = -1, dfs(), p[1] = 0; //Interaction Phase int a, b, cmd; DO_C(RD()){ RD(cmd, a, b); if (cmd == 1) Link(a, b); else if (cmd == 2) Cut(a, b); else if (cmd == 3) Modify(b, RD(), a); else Query(a, b); } puts(""); // Rececling ... RST(hd, p, l, r, delay, rev); }} |
（
下一阶段的任务。。我觉得动态树我还没弄明白。。还想在花一段时间。。
先打算先写一下动态树的那个「正当用途」 ———— 优化网络流。。
之后。。
我就去解决掉 fhq 的 1、2、3 。。三个难题。。(> <)。。。。
）
--- UPD ---
现在的搞法。
Alca
Amber
Belleve Invis
Chensiting123
Edward_mj
Fotile96
Hlworld
Kuangbin
Liyaos
Lwins
LYPenny
Mato 完整版
Mikeni2006
Mzry
Nagatsuki
Neko13
Oneplus
Rukata
Seter
Sevenkplus
Sevenzero
Shirleycrow
Vfleaking
wangzhpp
Watashi
WJMZBMR
Wywcgs
XadillaX
Yangzhe
三途川玉子
About.me
Vijos
