题解 P4219 【[BJOI2014]大融合】

· · 题解

看到很多人用 LCT 水过了此题，本人并没写过 LCT ，所以只好用一种笨办法，但是比 LCT 常数低太多。

对这个森林的操作只有不断地连边，而没有删边，我们不妨看成这本来是一棵树，接着不断有边被“点亮”，就合并了子树。最开始读一遍，把这颗树建出来，再重新扫一遍，连边的时候，用并查集维护每个节点所在树的根。

统计每个节点的子树大小。通过 (u, v) 边合并两颗树的时候 不妨设在大树中 u 是较高的，把较低的那颗树的大小加到大树上，把 u 一路到根节点的子树大小都加上 \mathrm{size}(v) 。这个是可以用树链剖分 + 树状数组维护的。

总复杂度 \Theta(n + q\log^2 n) 。常数原因比普通人写的 LCT 跑得还快。

注：样例代码只有开启 \texttt{C++11} 及以上版本才可以通过编译，这是因为作者弄巧成拙，强行动用了 \texttt{std::itoa()} 函数，其实没大用，就是缩行了一个循环赋值。

#include <cstdio>

#include <algorithm>
#include <numeric>

using namespace std;

struct edge {
    int v;
    edge* next;
};

const int N = 100010;

int n;
char opt[N];
int eu[N], ev[N], p[N], f[N], son[N], sum[N], fw[N], ord[N];
int top[N];
edge* g[N];

int find(int x);
void add_edge(int u, int v);
void dfs1(int u);
void dfs2(int u);
void change(int k, int x);
void tchange(int u, int x);
int query(int k);
int low_bit(int k);

int main() {
    int q;
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= q; ++i) {
        scanf(" %c%d%d", &opt[i], &eu[i], &ev[i]);
        if (opt[i] == 'A') {
            add_edge(eu[i], ev[i]);
            add_edge(ev[i], eu[i]);
        }
    }
    for (int u = 1; u <= n; ++u)
        if (!p[u]) {
            p[u] = -1;
            dfs1(u);
        }
    for (int u = 1; u <= n; ++u)
        if (p[u] == -1) {
            top[u] = u;
            dfs2(u);
        }
    iota(f + 1, f + n + 1, 1);
    for (int i = 1; i <= n; ++i) {
        tchange(i, 1);
        tchange(p[i], -1);
    }
    for (int i = 1; i <= q; ++i) {
        int u = eu[i], v = ev[i];
        if (p[u] == v)
            swap(u, v);
        int sv = query(ord[v]);
        if (opt[i] == 'A') {
            f[v] = find(u);
            tchange(u, sv);
            tchange(p[f[u]], -sv);
        } else {
            int s = query(ord[find(u)]);
            printf("%d\n", (s - sv) * sv);
        }
    }
    return 0;
}

void tchange(int u, int x) {
    while (u != -1) {
        change(ord[top[u]], x);
        change(ord[u] + 1, -x);
        u = p[top[u]];
    }
}

void dfs2(int u) {
    static int t;
    ord[u] = ++t;
    if (!son[u])
        return;
    top[son[u]] = top[u];
    dfs2(son[u]);
    for (edge* q = g[u]; q; q = q->next)
        if (p[q->v] == u && q->v != son[u]) {
            top[q->v] = q->v;
            dfs2(q->v);
        }
}

int low_bit(int k) {
    return k & -k;
}

void change(int k, int x) {
    for (; k <= n; k += low_bit(k))
        fw[k] += x;
}

int query(int k) {
    int ret = 0;
    for (; k; k -= low_bit(k))
        ret += fw[k];
    return ret;
}

void dfs1(int u) {
    sum[u] = 1;
    for (edge* q = g[u]; q; q = q->next)
        if (!p[q->v]) {
            p[q->v] = u;
            dfs1(q->v);
            sum[u] += sum[q->v];
            if (sum[son[u]] < sum[q->v])
                son[u] = q->v;
        }
}

int find(int x) {
    return f[x] == x ? x : (f[x] = find(f[x]));
}

void add_edge(int u, int v) {
    static edge pool[N * 2];
    static edge* p = pool;
    p->v = v;
    p->next = g[u];
    g[u] = p;
    ++p;
}