题目传送门(BZOJ)
>原文链接<

题解 :

LCT 维护子树信息模板题

连接一条边 : Link

查询一条边 : 我们只需要知道这个点子树的大小即可, 考虑用LCT维护这个信息

由于一般LCT中Splay某个节点的子树维护的是一条链而非子树的信息, 这之间的差别就是其他的虚链信息没有更新到父节点, 我们把虚链$siz$传递给父亲节点就好了

由于LCT认父不认子的特性, 我们不能在读取某个点的时候读取到它子树中有哪些虚链, 所以我们直接在从下往上更新的时候, 把这个点的虚链信息提前处理出来即可

设$siz[x]$为$x$的整个子树大小, $si[x]$表示这个点下面的所有虚链大小和, 那么$siz[x] = siz[ls]+siz[rs]+si[x]$

考虑在哪些操作的时候会改变$si[x]$

  1. 在Link时, 会加一条从$x$指向$y$的虚边, $si[y] += siz[x]$即可

  2. Access时, 会改变很多的实链信息, 其实就是断掉到原来$rs$的实边, 变成到$t$的,

    那么我们直接让$si[x] += siz[rs]-siz[t]$即可, 因为$t$从虚变实, 所以要减掉.

代码 :

#include <cstdio>#include <iostream>#define ll long longconst int N = 100010;using namespace std;#define ls ch[x][0]#define rs ch[x][1]#define Get(x) (ch[fa[x]][1] == x)#define isRoot(x) (ch[fa[x]][0] != x && ch[fa[x]][1] != x)int fa[N], ch[N][2], si[N], siz[N], rev[N];char opt[5];inline void pushUp(int x) { siz[x] = siz[ls] + siz[rs] + si[x] + 1;}inline void pushdown(int x) { if(rev[x]) { swap(ch[ls][0], ch[ls][1]), swap(ch[rs][0], ch[rs][1]); rev[ls] ^= 1, rev[rs] ^= 1, rev[x] = 0; }}void update(int x) { if(!isRoot(x)) update(fa[x]); pushdown(x);}inline void Rotate(int x) { int y = fa[x], z = fa[y], k = Get(x); if(!isRoot(y)) ch[z][ch[z][1]==y] = x; ch[y][k] = ch[x][!k], fa[ch[y][k]] = y; ch[x][!k] = y, fa[y] = x, fa[x] = z; pushUp(y), pushUp(x);}inline void Splay(int x) { update(x); for(int f; f = fa[x], !isRoot(x); Rotate(x)) { if(!isRoot(f)) Rotate(Get(f) == Get(x) ? f : x); }}void access(int x) { int t = 0; while(x) Splay(x), si[x] += siz[rs] - siz[t], rs = t, pushUp(x), t = x, x = fa[x];}inline void makeRoot(int x) { access(x), Splay(x), swap(ls, rs), rev[x] = 1;}inline void split(int x, int y) { makeRoot(x), makeRoot(y);}inline void link(int x, int y) { split(x, y), fa[x] = y, si[y] += siz[x], pushUp(y);}int main() { int n, m, x, y; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++) siz[i] = 1; while(m -- ) { scanf("%s%d%d", opt, &x, &y); if(opt[0] == 'A') link(x, y); else split(x, y), printf("%lld\n", (ll)siz[x]*(siz[y]-siz[x])); }}