题目地址：洛谷：【P4219】[BJOI2014]大融合 – 洛谷、BZOJ：Problem 4530. — [Bjoi2014]大融合

题目描述

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

例如，在上图中，现在一共有了5条边。其中，(3,8)这条边的负载是6，因为有六条简单路径2-3-8,2-3-8-7,3-8,3-8-7,4-3-8,4-3-8-7路过了(3,8)。
现在，你的任务就是随着边的添加，动态的回答小强对于某些边的负载的询问。

输入输出格式

输入格式：
第一行包含两个整数N,Q，表示星球的数量和操作的数量。星球从1开始编号。
接下来的Q行，每行是如下两种格式之一：
A x y 表示在x和y之间连一条边。保证之前x和y是不联通的。
Q x y 表示询问(x,y)这条边上的负载。保证x和y之间有一条边。
1≤N,Q≤100000

输出格式：
对每个查询操作，输出被查询的边的负载。

输入输出样例

输入样例#1：

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

输出样例#1：

6

题解

子树信息LCT的写法，对于每个点记录一个虚子树的大小，然后在access和link的时候维护一下轻重交替的信息就好。
复杂度$O(n \log n)$。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

inline char readsingle() {
    char c;
    while(!isalpha(c = fgc())) {}
    return c;
}

const int MAXN = 100005;

struct Node {
    int ch[2], fa, tsiz, siz;
    bool rev;
} tr[MAXN];

inline void update(int p) {
    tr[p].siz = tr[tr[p].ch[0]].siz + tr[tr[p].ch[1]].siz + tr[p].tsiz + 1;
}

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

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

inline void reverse(int p) {
    tr[p].rev ^= 1;
    std::swap(tr[p].ch[0], tr[p].ch[1]);
}

inline void pushdown(int p) {
    if(tr[p].rev) {
        if(tr[p].ch[0]) reverse(tr[p].ch[0]);
        if(tr[p].ch[1]) reverse(tr[p].ch[1]);
        tr[p].rev ^= 1;
    }
}

int sta[MAXN], stop;

inline void pushto(int p) {
    stop = 0;
    while(!isroot(p)) {
        sta[stop++] = p; p = tr[p].fa;
    }
    sta[stop++] = p;
    while(stop) {
        pushdown(sta[--stop]);
    }
}

inline void rotate(int p) {
    bool t = !isleft(p); int fa = tr[p].fa, ffa = tr[fa].fa;
    tr[p].fa = ffa; if(!isroot(fa)) tr[ffa].ch[!isleft(fa)] = p;
    tr[fa].ch[t] = tr[p].ch[!t]; tr[tr[fa].ch[t]].fa = fa;
    tr[p].ch[!t] = fa; tr[fa].fa = p;
    update(fa);
}

inline void splay(int p) {
    pushto(p);
    for(int fa = tr[p].fa; !isroot(p); rotate(p), fa = tr[p].fa) {
        if(!isroot(fa)) rotate(isleft(fa) == isleft(p) ? fa : p);
    }
    update(p);
}

inline void access(int p) {
    for(int q = 0; p; q = p, p = tr[p].fa) {
        splay(p); 
        tr[p].tsiz += tr[tr[p].ch[1]].siz;
        tr[p].tsiz -= tr[q].siz;
        tr[p].ch[1] = q; update(p);
    }
}

inline void makert(int p) {
    access(p); 
    splay(p); 
    reverse(p);
}

inline int findrt(int p) {
    access(p); splay(p);
    while(tr[p].ch[0]) p = tr[p].ch[0];
    return p;
}

inline void split(int u, int v) {
    makert(u); 
    access(v); 
    splay(v);
}

inline void link(int u, int v) {
    split(u, v); tr[u].fa = v; tr[v].tsiz += tr[u].siz; update(v);
}

inline void cut(int u, int v) {
    split(u, v);
    if(tr[v].ch[0] != u || tr[u].ch[1]) return;
    tr[v].ch[0] = tr[u].fa = 0;
}

int n, q;

int main() {
    n = readint(); q = readint();
    while(q--) {
        char op = readsingle();
        int x = readint(), y = readint();
        if(op == 'A') {
            link(x, y);
        } else {
            split(x, y);
            printf("%d\n", tr[x].siz * (tr[y].siz - tr[x].siz));
        }
    }
    return 0;
}