P4219 [BJOI2014]大融合

题目链接
小强要在 N N N 个孤立的星球上建立起一套通信系统。这套通信系统就是连接 N N N 个点的一个树。 这个树的边是一条一条添加上去的。在某个时刻，一条边的负载就是它所在的当前能够 联通的树上路过它的简单路径的数量。

例如，在上图中，现在一共有了 5 5 5 条边。其中， ( 3 , 8 ) (3,8) (3,8) 这条边的负载是 6 6 6，因为有六条简单路径 2 − 3 − 8 2-3-8 2−3−8, 2 − 3 − 8 − 7 2-3-8-7 2−3−8−7, 3 − 8 3-8 3−8, 3 − 8 − 7 3-8-7 3−8−7, 4 − 3 − 8 4-3-8 4−3−8, 4 − 3 − 8 − 7 4-3-8-7 4−3−8−7路过了 ( 3 , 8 ) (3,8) (3,8)。

现在，你的任务就是随着边的添加，动态的回答小强对于某些边的负载的询问。

输入格式
第一行包含两个整数 N , Q N, Q N,Q,表示星球的数量和操作的数量。星球从 1 1 1 开始编号。

接下来的 Q Q Q 行，每行是如下两种格式之一：

A x y 表示在 x x x和 y y y 之间连一条边。保证之前 x x x 和 y y y是不联通的。
Q x y 表示询问 ( x , y ) (x,y) (x,y) 这条边上的负载。保证 x x x 和 y y y 之间有一条边。
输出格式
对每个查询操作，输出被查询的边的负载。

输入输出样例
输入 #1

8 6
A 2 3
A 3 4
A 3 8
A 8 7
A 6 5
Q 3 8

输出 #1

6

说明/提示
对于所有数据， 1 ≤ N , Q ≤ 1 0 5 1≤N,Q≤10^5 1≤N,Q≤105

操作 2 2 2 实质上是断开询问边后统计两端点所在连通块内点的数量的乘积，这就需要维护对于每个点如果作为根则子树中的节点的数量。

设点 x x x 为根时子树中节点数量为 s i z 1 [ x ] siz1[x] siz1[x]， x x x 虚边相连的子树的节点的数量为 s i z 2 [ x ] siz2[x] siz2[x]，则 s i z 1 [ x ] = s i z 1 [ x l c ] + s i z 1 [ x r c ] + s i z 2 [ x ] + 1 siz1[x]=siz1[x_{lc}]+siz1[x_{rc}]+siz2[x]+1 siz1[x]=siz1[xlc​]+siz1[xrc​]+siz2[x]+1。

对于每次增加虚边的操作（link和access），需要更新 s i z 2 siz2 siz2 。

每次对子树节点数量进行操作需要将要操作的点转移为树根。

#include<bits/stdc++.h>

using namespace std;

inline int qr() {
    int f = 0, fu = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')fu = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        f = (f << 3) + (f << 1) + c - 48;
        c = getchar();
    }
    return f * fu;
}

const int N = 1e5 + 10;

struct LCT {
    struct node {
        int fa, ch[2], siz1, siz2;
        bool v;
    } tr[N];

    inline void upd(int p) {
        tr[p].siz1 = tr[tr[p].ch[0]].siz1 + tr[tr[p].ch[1]].siz1 + tr[p].siz2 + 1;
    }

    inline bool get(int p) {
        return p == tr[tr[p].fa].ch[1];
    }

    inline void spd(int p) {
        if (tr[p].v) {
            tr[p].v = false;
            swap(tr[p].ch[0], tr[p].ch[1]);
            if (tr[p].ch[0])tr[tr[p].ch[0]].v ^= 1;
            if (tr[p].ch[1])tr[tr[p].ch[1]].v ^= 1;
        }
    }

    inline bool isrt(int p) {
        return tr[tr[p].fa].ch[0] != p && tr[tr[p].fa].ch[1] != p;
    }

    inline void rot(int p) {
        int x = tr[p].fa, y = tr[x].fa, u = get(p), v = get(x);
        bool o = isrt(x);
        tr[tr[p].ch[u ^ 1]].fa = x, tr[x].ch[u] = tr[p].ch[u ^ 1];
        tr[x].fa = p, tr[p].ch[u ^ 1] = x, upd(x), upd(p);
        if ((tr[p].fa = y) && !o)tr[y].ch[v] = p;
    }

    stack<int> st;

    inline void pre(int p) {
        while (!isrt(p))st.push(p), p = tr[p].fa;
        spd(p);
        while (!st.empty())spd(st.top()), st.pop();
    }

    inline void splay(int p) {
        pre(p);
        for (int x = tr[p].fa; !isrt(p); rot(p), x = tr[p].fa)
            if (!isrt(x))rot(get(p) == get(x) ? x : p);
    }

    inline void access(int p) {
        for (int x = 0; p; p = tr[x = p].fa)
            splay(p), tr[p].siz2 += tr[tr[p].ch[1]].siz1 - tr[x].siz1, tr[p].ch[1] = x, upd(p);
    }

    inline void mkrt(int p) {
        access(p), splay(p), tr[p].v ^= 1;
    }

    inline void split(int x, int y) {
        mkrt(x), access(y), splay(y);
    }

    inline void link(int x, int y) {
        mkrt(x), mkrt(y), tr[x].fa = y, tr[y].siz2 += tr[x].siz1;
    }

    inline void cut(int x, int y) {
        split(x, y), tr[y].ch[0] = tr[x].fa = 0, upd(x), mkrt(x), mkrt(y);
    }
} L;

int m;
char o[2];

int main() {
    qr(), m = qr();
    while (m--) {
        scanf("%s", o);
        int x = qr(), y = qr();
        if (o[0] == 'A')L.link(x, y);
        else {
            L.cut(x, y);
            printf("%lld\n", 1ll * L.tr[x].siz1 * L.tr[y].siz1);
            L.link(x, y);
        }
    }
    return 0;
}