[Luogu P4219] [BJOI2014]大融合

题目描述

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

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

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

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

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

A x y 表示在x$x$ 和 y$y$ 之间连一条边。保证之前 x$x$ 和 y$y$ 是不联通的。
Q x y表示询问 (x,y)$(x,y)$ 这条边上的负载。保证 x$x$ 和 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

解题分析

显然答案是x$x$子树和y$y$子树大小相乘， 那么我们可以用LCT来维护连通性。

不过因为是维护子树， 我们需要知道虚子树的大小。 然后我们可以发现只有在splay的时候才可能涉及虚子树大小的改变， 那么我们只需在pushup的时候顺带维护即可。

代码如下：

#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <algorithm>
#define R register
#define IN inline
#define gc getchar()
#define W while
#define ls tree[now].son[0]
#define rs tree[now].son[1]
#define dad tree[now].fat
#define MX 100005
template <class T>
IN void in (T &x)
{
    x = 0; R char c = gc;
    W (!isdigit(c)) c = gc;
    W (isdigit(c))
    {x = (x << 1) + (x << 3) + c - 48, c = gc;}
}
namespace LCT
{
    struct Node
    {
        int son[2], fat, siz, vit;
        bool rev;
    }tree[MX];
    int st[MX], top, dot, num;
    IN bool nroot(const int &now) {return tree[dad].son[1] == now || tree[dad].son[0] == now;}
    IN bool get(const int &now){return tree[dad].son[1] == now;}
    IN void pushrev(const int &now)
    {std::swap(ls, rs); tree[now].rev ^= 1;}
    IN void pushup(const int &now)
    {tree[now].siz = 1 + tree[ls].siz + tree[rs].siz +tree[now].vit;}//统计子树个数
    IN void pushdown(const int &now)
    {
        if(tree[now].rev)
        {
            if(ls) pushrev(ls);
            if(rs) pushrev(rs);
            tree[now].rev = false;
        }
    }
    IN void rotate(const int &now)
    {
        R bool dir = get(now);
        R int fa = dad, grand = tree[fa].fat;
        tree[fa].son[dir] = tree[now].son[dir ^ 1];
        tree[tree[now].son[dir ^ 1]].fat = fa;
        if(nroot(fa)) tree[grand].son[get(fa)] = now;
        tree[now].fat = grand;
        tree[now].son[dir ^ 1] = fa;
        tree[fa].fat = now;
        pushup(fa);
    }
    IN void splay(const int &now)
    {
        R int fa, grand, x = now; top = 0;
        st[++top] = x;
        W (nroot(x)) x = tree[x].fat, st[++top] = x;
        W (top) pushdown(st[top--]);
        W (nroot(now))
        {
            fa = dad, grand = tree[fa].fat;
            if(nroot(fa)) rotate(get(now) == get(fa) ? fa : now);
            rotate(now);
        }
        pushup(now);
    }
    IN void access(int now)
    {
        for (R int x = 0; now; x = now, now = dad)
        {
            splay(now);
            tree[now].vit += tree[rs].siz;//右儿子被割掉， 虚儿子个数加上其子树大小
            rs = x;
            tree[now].vit -= tree[rs].siz;//成为了实儿子， 减去其子树大小
            pushup(now);
        }
    }
    IN void make_root(const int &now)
    {access(now), splay(now), pushrev(now);}
    IN void split(const int &x, const int &y)
    {make_root(x), access(y), splay(y);}
    IN void link(const int &x, const int &y)
    {
        split(x, y);
        tree[x].fat = y;
        tree[y].vit += tree[x].siz;
        pushup(y);
    }
}
using namespace LCT;
int main(void)
{
    char com[5];
    int a, b;
    in(dot), in(num);
    for (R int i = 1; i <= dot; ++i) tree[i].siz = 1;
    W (num--)
    {
        scanf("%s", com); in(a), in(b);
        if(com[0] == 'A') link(a, b);
        else
        {
            split(a, b);
            printf("%lld\n", 1ll * (tree[a].vit + 1) * (tree[b].vit + 1));
            //因为提链后只有a,b两个点，且b在a左上方， 那么b的虚儿子即为其右儿子，也就是它的子树， a的虚儿子个数也为其子树大小
        }
    }
}