• LCT

    LCT

    树链剖分

    常见的三种：重链、长链、轻实链。LCT 采用的是轻实链剖分。

    对于树上每一个点，将某一儿子作为实儿子，注意只有一个

    连向其的边设为实边，连向其他子树的边设为虚边。

    轻实边需要随着树形态的变化而改变

    LCT 支持如下操作：

    • 维护数链信息
    • 换根
    • 联通性
    • 动态连边、删边

    有了实儿子，还有两个定义：

    • 实边，连接父亲和实儿子的边。

    • 实链，实边构成的链。

    采用 splay 作为 LCT 的辅助树，有如下定义和性质

    • 一条实链的辅助树是维护这条链上节点的 splay

      每一颗 splay 维护一条从上到下深度严格递增的路径

    • 按照节点原树中的深度排序，可得中序遍历 splay 得到的点深度严格递增。

    • 一个节点仅在一棵 splay

    • 虚边总是由一棵 splay 指向另一个节点

      重要性质：认父不认子。

      即对于一个点，不会在 splay 中记录它的虚儿子，但是会在 splay 中记录它虚儿子的父亲为这个点

    实现

    平衡树

    实现其实是实现一个 splay 森林，支持区间翻转操作，点中编号就是原树的编号

    因为多个实链多个根，用函数 is_root 判断是否为根。(不过我习惯用 not_root )

    inline int nRt(int x) { return ch[fa[x]][0] == x || ch[fa[x]][1] == x; }

    splay 函数需要先将点 x 到根路径上的点从上到下 pushdown 一下，因为这里没有查询 kth 的操作。

    注意 pushup

    pushdown 也有讲究：当一个点打标记时，需保证左右儿子都在正确的位置上。

    1. inline void Up(int x) {
    2.     // push up
    3. }
    4. inline void rev(int x) { swap(ch[x][0], ch[x][1]), tg[x] ^= 1; }
    5. inline void down(int x) { if (tg[x]) rev(ch[x][0]), rev(ch[x][1]), tg[x] = 0; }
    6. inline int get(int x) { return ch[fa[x]][1] == x; }
    7. inline int nRt(int x) { return ch[fa[x]][0] == x || ch[fa[x]][1] == x; }
    8. inline void rot(int x) {
    9.     int y = fa[x], z = fa[y], k = get(x);
    10.     if (nRt(y)) ch[z][get(y)] = x; // important
    11.     fa[x] = z;
    12.     ch[y][k] = ch[x][k ^ 1], fa[ch[x][k ^ 1]] = y;
    13.     ch[x][k ^ 1] = y, fa[y] = x;
    14.     Up(y), Up(x);
    15. }
    16. inline void upd(int x) {
    17.     st[top = 1] = x;
    18.     while (nRt(x)) st[++top] = x = fa[x];
    19.     while (top) down(st[top--]);
    20. }
    21. inline void splay(int x) {
    22.     upd(x); // important
    23.     for (int y; y = fa[x], nRt(x); rot(x))
    24.         if (nRt(y)) rot(get(x) ^ get(y) ? x : y);
    25. }

    access

    LCT 的核心操作， access(x) 将 x" role="presentation" style="position: relative;">x 到原树根路径上的边全部变成实边。

    并且 x" role="presentation" style="position: relative;">x 为这一条实链的最后一个点，深度最大。

    即 x" role="presentation" style="position: relative;">x 与原先实儿子切断，x" role="presentation" style="position: relative;">x 到原树根路径上所有点构成一个 splay ，便于操作、查询

    1. inline void access(int x) {
    2.     for (int y = 0; x; x = fa[y = x])
    3.         splay(x), ch[x][1] = y, Up(x);
    4. }

    做法：不断将 x" role="presentation" style="position: relative;">x 旋转到当前 splay 的根，它的右儿子就是重儿子，需要修改。用变量 y" role="presentation" style="position: relative;">y 辅助

    注意： access 后 x" role="presentation" style="position: relative;">x 不一定为所得 splay 的根

    makeroot

    将 x" role="presentation" style="position: relative;">x 设为原树树根。

    1. inline void make(int x) {
    2.     access(x), splay(x), rev(x);
    3. }

    access + splay 后 x" role="presentation" style="position: relative;">x 转到了 splay 的根。

    此时 x" role="presentation" style="position: relative;">x 的深度最大，打上翻转标记后深度就最小了，成为了根

    findroot

    找到 x" role="presentation" style="position: relative;">x 在原树中的根

    1. inline int Find(int x) {
    2.     access(x), splay(x), down(x);
    3.     while (ch[x][0]) x = ch[x][0], down(x);
    4.     splay(x); // remember
    5.     return x;
    6. }

    同理， access + splay 后 x" role="presentation" style="position: relative;">x 深度最大，在 splay 的根节点。

    一直往左儿子走找到深度最小的点就是根节点。

    注意最后的 splay ，将原树根转回 splay 的根。等下会提到

    split

    split(x, y) 得到原树中 x" role="presentation" style="position: relative;">x 到 y" role="presentation" style="position: relative;">y 路径上的点组成的 splay ，并且 y" role="presentation" style="position: relative;">y 为根

    1. inline void split(int x, int y) {
    2.     make(x), access(y), splay(y);
    3. }

    先将 x" role="presentation" style="position: relative;">x 设为根，然后 access + splay 得到 y" role="presentation" style="position: relative;">y 到 x" role="presentation" style="position: relative;">x 的路径

    连一条 (x,y)" role="presentation" style="position: relative;">(x,y) 的轻边。

    1. inline void link(int x, int y) {
    2.     make(x);
    3.     if (Find(y) ^ x) fa[x] = y;
    4. }

    cut

    断掉边 (x,y)" role="presentation" style="position: relative;">(x,y)

    1. inline void cut(int x, int y) {
    2.     make(x);
    3.     if (Find(y) == x && fa[y] == x && !ch[y][0])
    4.         fa[y] = ch[x][1] = 0, Up(x);
    5. }

    注意判断的三个条件，确定存在边 (x,y)" role="presentation" style="position: relative;">(x,y)

    • 联通，将 x" role="presentation" style="position: relative;">x 设置为根。
    • splay 中父子关系，具体一点 y" role="presentation" style="position: relative;">y 是 x" role="presentation" style="position: relative;">x 的右儿子
    • x,y" role="presentation" style="position: relative;">x,y 之间没有点，即 y" role="presentation" style="position: relative;">y 没有左儿子

    此时体现在 findroot 中最后 splay 的作用了。将 splay 的根还原，再继续操作

    在一些写法中是没有这个操作的，导致后续的两个判断有些差异，单看这一个函数会觉得莫名其妙。

    edge

    实际上，判断是否存在边 (x,y)" role="presentation" style="position: relative;">(x,y) 是非常常用的函数。

    edge(x, y) 判断同一个树中，是否存在边 (x,y)" role="presentation" style="position: relative;">(x,y) ，借助 split(x, y) 实现

    1. inline bool edge(int x, int y) {
    2.     split(x, y);
    3.     return ch[y][0] == x && !ch[x][1];
    4. }

    code 模板

    模板

    1. #include 
    2. using namespace std;
    3. typedef unsigned long long uLL;
    4. typedef long double LD;
    5. typedef long long LL;
    6. typedef double db;
    7. const int N = 100005;
    8. int n, Ti, a[N], xo[N], ch[N][2], fa[N], tg[N], st[N], top;
    9. inline void Up(int x) { xo[x] = xo[ch[x][0]] ^ xo[ch[x][1]] ^ a[x]; }
    10. inline void rev(int x) { swap(ch[x][0], ch[x][1]), tg[x] ^= 1; }
    11. inline void down(int x) { if (tg[x]) rev(ch[x][0]), rev(ch[x][1]), tg[x] = 0; }
    12. inline int get(int x) { return ch[fa[x]][1] == x; }
    13. inline int nRt(int x) { return ch[fa[x]][0] == x || ch[fa[x]][1] == x; }
    14. inline void rot(int x) {
    15.     int y = fa[x], z = fa[y], k = get(x);
    16.     if (nRt(y)) ch[z][get(y)] = x;
    17.     fa[x] = z;
    18.     ch[y][k] = ch[x][k ^ 1], fa[ch[x][k ^ 1]] = y;
    19.     ch[x][k ^ 1] = y, fa[y] = x;
    20.     Up(y), Up(x);
    21. }
    22. inline void upd(int x) {
    23.     st[top = 1] = x;
    24.     while (nRt(x)) st[++top] = x = fa[x];
    25.     while (top) down(st[top--]);
    26. }
    27. inline void splay(int x) {
    28.     upd(x);
    29.     for (int y; y = fa[x], nRt(x); rot(x))
    30.         if (nRt(y)) rot(get(x) ^ get(y) ? x : y);
    31. }
    32. inline void access(int x) {
    33.     for (int y = 0; x; x = fa[y = x])
    34.         splay(x), ch[x][1] = y, Up(x);
    35. }
    36. inline void make(int x) {
    37.     access(x), splay(x), rev(x);
    38. }
    39. inline int Find(int x) {
    40.     access(x), splay(x), down(x);
    41.     while (ch[x][0]) x = ch[x][0], down(x);
    42.     splay(x);
    43.     return x;
    44. }
    45. inline void split(int x, int y) {
    46.     make(x), access(y), splay(y);
    47. }
    48. inline void link(int x, int y) {
    49.     make(x);
    50.     if (Find(y) ^ x) fa[x] = y;
    51. }
    52.  
    53. inline void cut(int x, int y) {
    54.     make(x);
    55.     if (Find(y) == x && fa[y] == x && !ch[y][0])
    56.         fa[y] = ch[x][1] = 0, Up(x);
    57. }
    58.  
    59. int main() {
    60.     scanf("%d%d", &n, &Ti);
    61.     for (int i = 1; i <= n; i++) scanf("%d", &a[i]), xo[i] = a[i];
    62.     for (int op, x, y; Ti--; ) {
    63.         scanf("%d%d%d", &op, &x, &y);
    64.         if (op == 0) split(x, y), printf("%d\n", xo[y]);
    65.         else if (op == 1) link(x, y);
    66.         else if (op == 2) cut(x, y);
    67.         else if (op == 3) splay(x), a[x] = y, Up(x);
    68.     }
    69. }

    应用

    维护联通性

    比较简单。直接用 findroot 判断。

    [SDOI2008] 洞穴勘测

    1. #include 
    2. using namespace std;
    3. typedef unsigned long long uLL;
    4. typedef long double LD;
    5. typedef long long LL;
    6. typedef double db;
    7. const int N = 10005;
    8. char buf[100000], *S = buf, *T = buf;
    9. inline char G() {
    10.     return S == T && (T = (S = buf) + fread(buf, 1, 100000, stdin), S == T) ? EOF : *S++;
    11. }
    12. inline int Rd() {
    13.     register int x = 0;
    14.     char C = G();
    15.     for (; C < '0' || C > '9'; C = G()) ;
    16.     for (; C > '/' && C < ':'; C = G()) x = (x << 1) + (x << 3) + (C ^ 48);
    17.     return x;
    18. }
    19. int n, TT;
    20. int st[N], top;
    21. int fa[N], ch[N][2], tg[N];
    22. char op;
    23. /*
    24. LCT here
    25. */
    26. int main() {
    27.     n = Rd(), TT = Rd();
    28.     for (int x, y; TT--; ) {
    29.         op = G();
    30.         while (op < 'A' || op > 'Z') op = G();
    31.         x = Rd(), y = Rd();
    32.         if (op == 'C') link(x, y);
    33.         else if (op == 'D') cut(x, y);
    34.         else puts(Find(x) == Find(y) ? "Yes" : "No");
    35.     }
    36. }

    维护树链信息

    比较简单，用 split 结合各种标记维护。

    [国家集训队]Tree II

    注意懒标记优先级。由于题目保证联通，link,cut 可以不判断联通性

    同时这是国集的题，数据很强，如果硬要在判断联通性，一定不能打假，否则可能调一上午。。。

    1. #include 
    2. #define int long long
    3. using namespace std;
    4. typedef unsigned long long uLL;
    5. typedef long double LD;
    6. typedef long long LL;
    7. typedef double db;
    8. const int N = 100005;
    9. const LL P = 51061;
    10. int n, T, ch[N][2], fa[N], st[N], top;
    11. LL val[N], sm[N], tg[N], ad[N], mu[N], sz[N];
    12. char op[5];
    13. inline int get(int x) { return ch[fa[x]][1] == x; }
    14. inline int nRt(int x) { return ch[fa[x]][0] == x || ch[fa[x]][1] == x; }
    15. inline void Up(int x) {
    16.     sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
    17.     sm[x] = (sm[ch[x][0]] + sm[ch[x][1]] + val[x]) % P;
    18. }
    19. inline void rev(int x) { swap(ch[x][0], ch[x][1]), tg[x] ^= 1; }
    20. inline void mul(int x, LL v) {
    21.     (mu[x] *= v) %= P;
    22.     (ad[x] *= v) %= P;
    23.     (sm[x] *= v) %= P;
    24.     (val[x] *= v) %= P;
    25. }
    26. inline void add(int x, LL v) {
    27.     (ad[x] += v) %= P;
    28.     (sm[x] += v * sz[x]) %= P;
    29.     (val[x] += v) %= P;
    30. }
    31. inline void down(int x) {
    32.     if (mu[x] != 1) mul(ch[x][0], mu[x]), mul(ch[x][1], mu[x]), mu[x] = 1;
    33.     if (ad[x]) add(ch[x][0], ad[x]), add(ch[x][1], ad[x]), ad[x] = 0;
    34.     if (tg[x]) {
    35.         if (ch[x][0]) rev(ch[x][0]);
    36.         if (ch[x][1]) rev(ch[x][1]);
    37.         tg[x] = 0;
    38.     }
    39. }
    40. inline void rot(int x) {
    41.     int y = fa[x], z = fa[y], k = get(x);
    42.     if (nRt(y)) ch[z][get(y)] = x;
    43.     fa[x] = z;
    44.     if (ch[x][k ^ 1]) fa[ch[x][k ^ 1]] = y;
    45.     ch[y][k] = ch[x][k ^ 1];
    46.     ch[x][k ^ 1] = y, fa[y] = x;
    47.     Up(y), Up(x);
    48. }
    49. inline void upd(int x) {
    50.     st[top = 1] = x;
    51.     while (nRt(x)) st[++top] = x = fa[x];
    52.     while (top) down(st[top--]);
    53. }
    54. inline void splay(int x) {
    55.     upd(x);
    56.     for (int y; y = fa[x], nRt(x); rot(x))
    57.         if (nRt(y)) rot(get(x) ^ get(y) ? x : y);
    58. }
    59. inline void access(int x) { for (int y = 0; x; x = fa[y = x]) splay(x), ch[x][1] = y, Up(x); }
    60. inline void make(int x) { access(x), splay(x), rev(x); }
    61. inline int Find(int x) {
    62.     access(x), splay(x), down(x);
    63.     while (ch[x][0]) x = ch[x][0], down(x);
    64.     splay(x);
    65.     return x;
    66. }
    67. inline void link(int x, int y) {
    68.     make(x);
    69.     if (Find(y) != x) fa[x] = y;
    70. }
    71. inline void cut(int x, int y) {
    72.     make(x);
    73.     if (Find(y) == x && fa[y] == x && !ch[y][0])
    74.         fa[y] = ch[x][1] = 0, Up(x);
    75. }
    76. inline void split(int x, int y) { make(x), access(y), splay(y); }
    77. signed main() {
    78.     // freopen("1.in", "r", stdin);
    79.     // freopen("1.out", "w", stdout);
    80.     scanf("%lld%lld", &n, &T);
    81.     for (int i = 1; i <= n; i++) val[i] = mu[i] = sz[i] = 1;
    82.     for (int i = 1, u, v; i < n; i++) {
    83.         scanf("%lld%lld", &u, &v);
    84.         link(u, v);
    85.     }
    86.     for (int u, v, w; T--; ) {
    87.         scanf("%s%lld%lld", op, &u, &v);
    88.         if (op[0] == '*') {
    89.             scanf("%lld", &w);
    90.             split(u, v);
    91.             mul(v, 1ll * w);
    92.         } else if (op[0] == '+') {
    93.             scanf("%lld", &w);
    94.             split(u, v);
    95.             add(v, 1ll * w);
    96.         } else if (op[0] == '/') {
    97.             split(u, v);
    98.             printf("%lld\n", sm[v]);
    99.         } else if (op[0] == '-') {
    100.             cut(u, v);
    101.             scanf("%lld%lld", &u, &v);
    102.             link(u, v);
    103.         }
    104.     }
    105. }

    维护生成树

    重要。

    以 最小生成树 为例，用类似 kruskal 的思路就是依次加入边

    如果加入边 (u,v,w)" role="presentation" style="position: relative;">(u,v,w) 形成了环，就选出 (u,v)" role="presentation" style="position: relative;">(u,v) 链上边权最大的一条边 (u′,v′,w′)" role="presentation" style="position: relative;">(u′,v′,w′)

    如果满足 w<w′" role="presentation" style="position: relative;">w<w′ 就删除边 (u′,v′)" role="presentation" style="position: relative;">(u′,v′) 并加入边 (u,v,w)" role="presentation" style="position: relative;">(u,v,w) ，否则不加入。

    加入所有边后即可得到最小生成树，无需对边权排序

    由于 lct 的形态会不断变化，难以直接维护边权。处理方法是拆边。

    将边权放在代表边的点权里，代表点的点权设为 0 。这样可以只维护点权，是可以实现的操作。

    1. #include 
    2. using namespace std;
    3. const int N = 250005;
    4. int n, m, a[N], id[N], mx[N], fa[N], ch[N][2], st[N], top, tg[N], tot, ans, use;
    5. inline void Up(int x) {
    6.     mx[x] = a[x], id[x] = x;
    7.     if (mx[x] < mx[ch[x][0]]) mx[x] = mx[ch[x][0]], id[x] = id[ch[x][0]];
    8.     if (mx[x] < mx[ch[x][1]]) mx[x] = mx[ch[x][1]], id[x] = id[ch[x][1]];
    9. }
    10. /*
    11. LCT here
    12. */
    13. inline int chk(int x, int y) { return make(x), Find(y) == x; }
    14. int main() {
    15.     scanf("%d%d", &n, &m);
    16.     tot = n;
    17.     for (int i = 1, u, v, w, nw; i <= m; i++) {
    18.         ++tot;
    19.         scanf("%d%d%d", &u, &v, &w), a[tot] = w;
    20.         if (!chk(u, v)) link(u, tot), link(v, tot), ans += w, ++use;
    21.         else {
    22.             split(u, v);
    23.             if (mx[v] <= w) continue;
    24.             nw = id[v];
    25.             ans += w - mx[v], splay(nw);
    26.             fa[ch[nw][0]] = fa[ch[nw][1]] = 0;
    27.             ch[nw][0] = ch[nw][1] = 0;
    28.             link(u, tot), link(v, tot);
    29.         }
    30.     }
    31.     if (use == n - 1) printf("%d", ans);
    32.     else puts("orz");
    33. }

    例 魔法森林

    魔法森林

    边权由 (a,b)" role="presentation" style="position: relative;">(a,b) 表示，要求从 1 到 n" role="presentation" style="position: relative;">n 路径上(( a" role="presentation" style="position: relative;">a 的最大值)和( b" role="presentation" style="position: relative;">b 的最大值)之和)最小。

    按照 b" role="presentation" style="position: relative;">b 排序，维护 a" role="presentation" style="position: relative;">a 的最小生成树。

    1. #include 
    2. using namespace std;
    3. typedef unsigned long long uLL;
    4. typedef long double LD;
    5. typedef long long LL;
    6. typedef double db;
    7. const int N = 200005;
    8. int n, m, ff[N], val[N], id[N], fa[N], ch[N][2], st[N], tg[N], ans = 2e9;
    9. struct Edge { int u, v, a, b; } e[N];
    10. inline bool cmp(Edge A, Edge B) {
    11.     return A.b < B.b;
    12. }
    13. inline int gmx(int x, int y) { return val[x] > val[y] ? x : y; }
    14. inline void Up(int x) { id[x] = gmx(x, gmx(id[ch[x][0]], id[ch[x][1]])); }
    15. inline int get(int x) { return ch[fa[x]][1] == x; }
    16. inline bool nRt(int x) { return ch[fa[x]][0] == x || ch[fa[x]][1] == x; }
    17. inline void rev(int x) { tg[x] ^= 1, swap(ch[x][0], ch[x][1]); }
    18. inline void down(int x) { if (tg[x]) rev(ch[x][0]), rev(ch[x][1]), tg[x] = 0; }
    19. inline void rot(int x) {
    20.     register int y = fa[x], z = fa[y], k = get(x);
    21.     if (nRt(y)) ch[z][get(y)] = x;
    22.     fa[x] = z;
    23.     ch[y][k] = ch[x][k ^ 1], fa[ch[x][k ^ 1]] = y;
    24.     ch[x][k ^ 1] = y, fa[y] = x;
    25.     Up(y), Up(x);
    26. }
    27. inline void splay(int x) {
    28.     register int top, k = x;
    29.     st[top = 1] = k;
    30.     while (nRt(k)) st[++top] = k = fa[k];
    31.     while (top) down(st[top--]);
    32.     for (int y; y = fa[x], nRt(x); rot(x))
    33.         if (nRt(y)) rot(get(x) ^ get(y) ? x : y);
    34. }
    35. inline void access(int x) { for (int y = 0; x; x = fa[y = x]) splay(x), ch[x][1] = y, Up(x); }
    36. inline void make(int x) { access(x), splay(x), rev(x); }
    37. inline void split(int x, int y) { make(x), access(y), splay(y); }
    38. int fd(int x) { return ff[x] == x ? x : ff[x] = fd(ff[x]); }
    39. inline int Find(int x) {
    40.     access(x), splay(x), down(x);
    41.     while (ch[x][0]) down(x = ch[x][0]);
    42.     return splay(x), x;
    43. }
    44. inline void link(int x, int y) {
    45.     make(x);
    46.     if (Find(y) ^ x) fa[x] = y;
    47. }
    48. inline void cut(int x, int y) {
    49.     make(x);
    50.     if (Find(y) == x && fa[y] == x && ch[x][1] == y)
    51.         fa[y] = ch[x][1] = 0, Up(x);
    52. }
    53. int main() {
    54.     scanf("%d%d", &n, &m);
    55.     for (int i = 1; i <= n + m; i++) ff[i] = id[i] = i;
    56.     for (int i = 1; i <= m; i++) {
    57.         scanf("%d%d%d%d", &e[i].u, &e[i].v, &e[i].a, &e[i].b);
    58.     }
    59.     sort(e + 1, e + m + 1, cmp);
    60.     for (int i = 1; i <= m; i++) val[i + n] = e[i].a;
    61.     for (int i = 1, u, v, p, q, fl, o; i <= m; i++) {
    62.         p = fd(u = e[i].u), q = fd(v = e[i].v), fl = 1;
    63.         if (u == v) continue;
    64.         if (p == q) {
    65.             split(u, v), o = id[v];
    66.             if (val[o] > e[i].a) cut(e[o - n].u, o), cut(o, e[o - n].v);
    67.             else fl = 0;
    68.         } else ff[p] = q;
    69.         if (fl) link(u, i + n), link(i + n, v);
    70.         if (fd(1) == fd(n)) split(1, n), ans = min(ans, e[i].b + val[id[n]]);
    71.     }
    72.     if (ans == 2e9) puts("-1");
    73.     else printf("%d", ans);
    74. }

    维护边双

    用 LCT 的一个点表示一个边双。外面用一个并查集维护每个点属于哪一个边拴。

    加入边时，如果不联通就 link

    否则，形成的环构成一个边双，把环缩成一个点，把并查集也合并。

    • 暴力缩点：将当前辅助树的根节点设置为集合的标志节点， dfs 整个辅助树

      把其他点的并查集祖先修改。并断开标志节点与子树的连接，暴力修改不会超过 nlog⁡n" role="presentation" style="position: relative;">nlog⁡n 次

    [AHOI2005] 航线规划

    离线显然，查询其实就是(路径上边双个数减一)。

    每用一个点用并查集找到它所在边双，例如 access 时 x←find(fax)" role="presentation" style="position: relative;">x←find(fax)

    1. #include 
    2. using namespace std;
    3. typedef unsigned long long uLL;
    4. typedef long double LD;
    5. typedef long long LL;
    6. typedef double db;
    7. const int N = 1e5 + 5;
    8. int n, m, Ti, ty[N], ans[N], outs, dl[N], fa[N], ch[N][2], tg[N], sz[N], st[N], ff[N], qu[N], qv[N];
    9. struct edge {
    10.     int u, v;
    11.     bool operator < (edge A) const {
    12.         if (u ^ A.u) return u < A.u;
    13.         return v < A.v;
    14.     }
    15. } E[N];
    16. int fd(int x) { return ff[x] == x ? x : ff[x] = fd(ff[x]); }
    17. inline void Up(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1; }
    18. inline int get(int x) { return ch[fd(fa[x])][1] == x; }
    19. inline int nRt(int x) { return ch[fd(fa[x])][0] == x || ch[fd(fa[x])][1] == x; }
    20. inline void rev(int x) { tg[x] ^= 1, swap(ch[x][0], ch[x][1]); }
    21. inline void down(int x) { if (tg[x]) rev(ch[x][0]), rev(ch[x][1]), tg[x] = 0; }
    22. inline void rot(int x) {
    23.     register int y = fd(fa[x]), z = fd(fa[y]), k = get(x);
    24.     if (nRt(y)) ch[z][get(y)] = x;
    25.     fa[x] = z;
    26.     ch[y][k] = ch[x][k ^ 1], fa[ch[x][k ^ 1]] = y;
    27.     ch[x][k ^ 1] = y, fa[y] = x;
    28.     Up(y), Up(x);
    29. }
    30. inline void splay(int x) {
    31.     register int top, k = x;
    32.     st[top = 1] = k;
    33.     while (nRt(k)) st[++top] = k = fd(fa[k]);
    34.     while (top) down(st[top--]);
    35.     for (int y; y = fd(fa[x]), nRt(x); rot(x))
    36.         if (nRt(y)) rot(get(x) ^ get(y) ? x : y);
    37. }
    38. inline void access(int x) { for (int y = 0; x; y = x, x = fd(fa[x])) splay(x), ch[x][1] = y, Up(x); }
    39. inline void make(int x) { access(x), splay(x), rev(x); }
    40. inline int Find(int x) {
    41.     access(x), splay(x), down(x);
    42.     while (ch[x][0]) down(x = ch[x][0]);
    43.     return splay(x), x;
    44. }
    45. inline void split(int x, int y) { make(y), access(x), splay(x); }
    46. void del(int x, int y) {
    47.     if (x) ff[x] = y, sz[y] += sz[x], del(ch[x][0], y), del(ch[x][1], y);
    48. }
    49. inline void mer(int x, int y) {
    50.     if (x == y) return;
    51.     make(x);
    52.     if (Find(y) ^ x) { fa[x] = y; return; }
    53.     del(ch[x][1], x), ch[x][1] = 0, Up(x);
    54. }
    55. int main() {
    56.     scanf("%d%d", &n, &m);
    57.     for (int i = 1; i <= n; i++) sz[i] = 1, ff[i] = i;
    58.     for (int i = 1; i <= m; i++) {
    59.         scanf("%d%d", &E[i].u, &E[i].v);
    60.         if (E[i].u > E[i].v) swap(E[i].u, E[i].v);
    61.     }
    62.     sort(E + 1, E + m + 1);
    63.     for (int op, u, v; scanf("%d", &op), op != -1;) {
    64.         scanf("%d%d", &u, &v);
    65.         if (u > v) swap(u, v);
    66.         ++Ti, qu[Ti] = u, qv[Ti] = v, ty[Ti] = op;
    67.         if (!op) dl[lower_bound(E + 1, E + m + 1, (edge){ u, v }) - E] = 1;
    68.     }
    69.     for (int i = 1; i <= m; i++)
    70.         if (!dl[i]) mer(fd(E[i].u), fd(E[i].v));
    71.     for (int x, y; Ti; --Ti) {
    72.         x = fd(qu[Ti]), y = fd(qv[Ti]);
    73.         if (ty[Ti]) split(x, y), ans[++outs] = sz[x] - 1;
    74.         else mer(x, y);
    75.     }
    76.     while (outs) printf("%d\n", ans[outs--]);
    77. }

    维护子树信息

    lct 最大痛点，树剖在这里由不可取代的地位。

    常见的是维护子树信息总和，如大小、权值。

    以 [BJOI2014]大融合 为例

    查询就是 cut(x,y) 后两个子树大小的乘积。

    用多一个数组 s2" role="presentation" style="position: relative;">s2 记录虚儿子的信息，注意 s" role="presentation" style="position: relative;">s 为所有儿子的信息，包括实儿子

    需要修改 pushup, access, link

    就是根据虚实边的转化修改。

    1. #include 
    2. using namespace std;
    3. typedef unsigned long long uLL;
    4. typedef long double LD;
    5. typedef long long LL;
    6. typedef double db;
    7. char buf[100000], *S = buf, *T = buf;
    8. inline char G() {
    9.     return S == T && (T = (S = buf) + fread(buf, 1, 100000, stdin), S == T) ? EOF : *S++;
    10. }
    11. inline int Rd() {
    12.     register int x = 0;
    13.     static char C = G();
    14.     for (; C < '0' || C > '9'; C = G()) ;
    15.     for (; C > '/' && C < ':'; C = G()) x = (x << 1) + (x << 3) + (C ^ 48);
    16.     return x;
    17. }
    18. const int N = 100005;
    19. int n, Ti, tg[N], sz[N], sz2[N], fa[N], ch[N][2], st[N], top;
    20. char op;
    21. inline int get(int x) { return ch[fa[x]][1] == x; }
    22. inline int nRt(int x) { return ch[fa[x]][0] == x || ch[fa[x]][1] == x; }
    23. inline void Up(int x) { sz[0] = 0, sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1 + sz2[x]; }
    24. inline void rev(int x) { swap(ch[x][0], ch[x][1]), tg[x] ^= 1; }
    25. inline void down(int x) { if (tg[x]) rev(ch[x][0]), rev(ch[x][1]), tg[x] = 0; }
    26. inline void rot(int x) {
    27.     int y = fa[x], z = fa[y], k = get(x);
    28.     if (nRt(y)) ch[z][get(y)] = x;
    29.     fa[x] = z;
    30.     ch[y][k] = ch[x][k ^ 1], fa[ch[x][k ^ 1]] = y;时
    31.     ch[x][k ^ 1] = y, fa[y] = x;
    32.     Up(y), Up(x);
    33. }
    34. inline void upd(int x) {
    35.     st[top = 1] = x;
    36.     while (nRt(x)) st[++top] = x = fa[x];
    37.     while (top) down(st[top--]);
    38. }
    39. inline void splay(int x) {
    40.     upd(x);
    41.     for (int y; y = fa[x], nRt(x); rot(x))
    42.         if (nRt(y)) rot(get(x) ^ get(y) ? x : y);
    43. }
    44. inline void access(int x) {
    45.     for (int y = 0; x; x = fa[y = x])
    46.         splay(x), sz2[x] += sz[ch[x][1]] - sz[y], ch[x][1] = y, Up(x);
    47. }
    48. inline void make(int x) { access(x), splay(x), rev(x); }
    49. inline int Find(int x) {
    50.     access(x), splay(x), down(x);
    51.     while (ch[x][0]) down(x = ch[x][0]);
    52.     return splay(x), x;
    53. }
    54. inline void link(int x, int y) {
    55.     make(x), make(y), fa[x] = y, sz2[y] += sz[x], Up(y);
    56. }
    57. inline void cut(int x, int y) {
    58.     make(x), Find(y), fa[y] = ch[x][1] = 0, Up(x);
    59. }
    60. int main() {
    61.     n = Rd(), Ti = Rd();
    62.     for (int x, y; Ti--; ) {
    63.         op = G();
    64.         while (op < 'A' || op > 'Z') op = G();
    65.         x = Rd(), y = Rd();
    66.         if (op == 'A') link(x, y);
    67.         else {
    68.             cut(x, y), make(x), make(y);
    69.             printf("%lld\n", 1ll * sz[x] * sz[y]);
    70.             link(x, y);
    71.         }
    72.     }
    73. }
  • 相关阅读:
    C++ realloc()用法及代码示例
    车道线检测-LSTR-论文学习笔记
    ＜C++＞详解list类
    安全测试之探索 windows 游戏扫雷
    Docker部署clickhouse
    【数据分享】厦门市共享单车数据
    SpringBoot获取树状结构数据
    体育场馆预约小程序,体育馆预约小程序,体育馆预约系统小程序
    C语言、C++操作符优先级
    Java项目：SSM网上家具商城网站系统平台
  • 原文地址：https://blog.csdn.net/KonjakuLAF/article/details/126314184