2018-ACetic_ACid/LCT

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <bits/stdc++.h>
#define N 100010
using namespace std;
int fa[N], c[2][N], si[N], sum[N], rev[N], val[N];

void pushup(int x)
{
    sum[x] = sum[c[0][x]] + sum[c[1][x]] + si[x] + val[x];
}

void pushdown(int x)
{
    if (rev[x])
    {
        int l = c[0][x], r = c[1][x];
        swap(c[0][l], c[1][l]), swap(c[0][r], c[1][r]);
        rev[l] ^= 1, rev[r] ^= 1, rev[x] = 0;
    }
}

bool isroot(int x)
{
    return c[0][fa[x]] != x && c[1][fa[x]] != x;
}

void update(int x)
{
    if (!isroot(x))
        update(fa[x]);
    pushdown(x);
}

void rotate(int x)
{
    int y = fa[x], z = fa[y], l = (c[1][y] == x), r = l ^ 1;
    if (!isroot(y))
        c[c[1][z] == y][z] = x;
    fa[x] = z, fa[y] = x, fa[c[r][x]] = y, c[l][y] = c[r][x], c[r][x] = y;
    pushup(y), pushup(x);
}

void splay(int x)
{
    update(x);
    while (!isroot(x))
    {
        int y = fa[x], z = fa[y];
        if (!isroot(y))
        {
            if ((c[0][y] == x) ^ (c[0][z] == y))
                rotate(x);
            else
                rotate(y);
        }
        rotate(x);
    }
}

void access(int x)
{
    int t = 0;
    while (x)
        splay(x), si[x] += sum[c[1][x]] - sum[t], c[1][x] = t, pushup(x), t = x, x = fa[x];
}

void makeroot(int x)
{
    access(x), splay(x), swap(c[0][x], c[1][x]), rev[x] = 1;
}

void split(int x, int y)
{
    makeroot(x), makeroot(y);
}

void link(int x, int y)
{
    split(x, y), fa[x] = y, si[y] += sum[x], pushup(y);
}

void cut(int x, int y)
{
    makeroot(x), access(y), splay(y), c[0][y] = fa[x] = 0, pushup(y);
}

int findroot(int x)
{
    access(x); splay(x);
    pushdown(x);
    while (c[0][x]) pushdown(x = c[0][x]);
    return x;
}

int findfa(int x)
{
    access(x); splay(x);
    pushdown(x);
    int t = c[0][x];
    pushdown(t);
    while (c[1][t]) pushdown(t = c[1][t]);
    return t;
}

}}}

#include <bits/stdc++.h>
#define N 100010
using namespace std;
int fa[N], c[2][N], si[N], sum[N], rev[N], val[N];
void pushup(int x)
{
    sum[x] = sum[c[0][x]] + sum[c[1][x]] + si[x] + val[x];
}
void pushdown(int x)
{
    if (rev[x])
    {
        int l = c[0][x], r = c[1][x];
        swap(c[0][l], c[1][l]), swap(c[0][r], c[1][r]);
        rev[l] ^= 1, rev[r] ^= 1, rev[x] = 0;
    }
}
bool isroot(int x)
{
    return c[0][fa[x]] != x && c[1][fa[x]] != x;
}
void update(int x)
{
    if (!isroot(x))
        update(fa[x]);
    pushdown(x);
}
void rotate(int x)
{
    int y = fa[x], z = fa[y], l = (c[1][y] == x), r = l ^ 1;
    if (!isroot(y))
        c[c[1][z] == y][z] = x;
    fa[x] = z, fa[y] = x, fa[c[r][x]] = y, c[l][y] = c[r][x], c[r][x] = y;
    pushup(y), pushup(x);
}
void splay(int x)
{
    update(x);
    while (!isroot(x))
    {
        int y = fa[x], z = fa[y];
        if (!isroot(y))
        {
            if ((c[0][y] == x) ^ (c[0][z] == y))
                rotate(x);
            else
                rotate(y);
        }
        rotate(x);
    }
}
void access(int x)
{
    int t = 0;
    while (x)
        splay(x), si[x] += sum[c[1][x]] - sum[t], c[1][x] = t, pushup(x), t = x, x = fa[x];
}
void makeroot(int x)
{
    access(x), splay(x), swap(c[0][x], c[1][x]), rev[x] = 1;
}
void split(int x, int y)
{
    makeroot(x), makeroot(y);
}
void link(int x, int y)
{
    split(x, y), fa[x] = y, si[y] += sum[x], pushup(y);
}
void cut(int x, int y)
{
    makeroot(x), access(y), splay(y), c[0][y] = fa[x] = 0, pushup(y);
}
int findroot(int x)
{
    access(x); splay(x);
    pushdown(x);
    while (c[0][x]) pushdown(x = c[0][x]);
    return x;
}
int findfa(int x)
{
    access(x); splay(x);
    pushdown(x);
    int t = c[0][x];
    pushdown(t);
    while (c[1][t]) pushdown(t = c[1][t]);
    return t;
}