题目链接：LOJ 2230

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

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

数据范围：$1\le n,q\le 10^5$。

Solution

看到动态加边、查询子树大小，肯定是 $\text{LCT}$ 啦！直接维护每个节点的子树信息（虚子树大小、总大小等），然后查询 $(u,v)$ 时我们提取出这条链，然后答案就是 $u,v​$ 虚子树大小加上他们本身的乘积。

时间复杂度：$\mathcal O(q\log n)$。

Code

#include <cstdio>
#include <algorithm>

const int N = 1e5 + 5;

int n, m;

struct Node;
Node *null;

struct Node {
    Node *ch[2], *fa;
    int sz, si;
    bool rev;
    Node() {
        ch[0] = ch[1] = fa = null;
        sz = 1, si = rev = 0;
    }
    bool get() {
        return fa->ch[1] == this;
    }
    bool isroot() {
        return fa->ch[0] != this && fa->ch[1] != this;
    }
    void reverse() {
        rev ^= 1;
        std::swap(ch[0], ch[1]);
    }
    void pushup() {
        sz = ch[0]->sz + ch[1]->sz + si + 1;
    }
    void pushdown() {
        if (rev) {
            ch[0]->reverse();
            ch[1]->reverse();
            rev = 0;
        }
    }
} *a[N];

struct LCT {
    LCT(int n) {
        null = new Node();
        null->ch[0] = null->ch[1] = null->fa = null;
        null->sz = 0;
        for (int i = 1; i <= n; i++) {
            a[i] = new Node();
        }
    }
    void pushtag(Node *x) {
        if(!x->isroot()) pushtag(x->fa);
        x->pushdown();
    }
    void rotate(Node *x) {
        Node *y = x->fa, *z = y->fa;
        int k = x->get();
        !y->isroot() && (z->ch[y->get()] = x), x->fa = z;
        y->ch[k] = x->ch[!k], x->ch[!k]->fa = y;
        x->ch[!k] = y, y->fa = x;
        y->pushup();
    }
    void splay(Node *x) {
        pushtag(x);
        while (!x->isroot()) {
            Node *y = x->fa;
            if (!y->isroot()) {
                rotate(x->get() == y->get() ? y : x);
            }
            rotate(x);
        }
        x->pushup();
    }
    void access(Node *x) {
        for (Node *y = null; x != null; x = (y = x)->fa) {
            splay(x);
            x->si += x->ch[1]->sz;
            x->si -= (x->ch[1] = y)->sz;
            x->pushup();
        }
    }
    void makeroot(Node *x) {
        access(x), splay(x), x->reverse();
    }
    Node *findroot(Node *x) {
        access(x), splay(x);
        x->pushdown();
        while (x->ch[0] != null) {
            (x = x->ch[0])->pushdown();
        }
        return x;
    }
    void split(Node *x, Node *y) {
        makeroot(x), access(y), splay(y);
    }
    void link(Node *x, Node *y) {
        makeroot(x);
        if (findroot(y) != x) {
            (x->fa = y)->si += x->sz, y->pushup();
        }
    }
    void cut(Node *x, Node *y) {
        makeroot(x);
        if (findroot(y) == x && x->fa == y && x->ch[1] == null) {
            x->fa = y->ch[0] = null, y->pushup();
        }
    }
};

int main() {
    scanf("%d%d", &n, &m);
    LCT lct(n);
    for (int i = 1; i <= m; i++) {
        char s[5];
        int u, v;
        scanf("%s%d%d", s + 1, &u, &v);
        if (s[1] == 'A') {
            lct.link(a[u], a[v]);
        } else {
            lct.split(a[u], a[v]);
            printf("%lld\n", 1LL * (a[u]->si + 1) * (a[v]->si + 1));
        }
    }
    return 0;
}