题解 P4219 【[BJOI2014]大融合】

· · 题解

好像没有树剖的题解啊

由于这题没有删边操作

然后又没有强制在线

我们可以把最终形成的森林的形态建出来

我们可以建一个超级root　将森林变成树

我们维护每一阶段的每个点子树大小（节点个数），同时用并查集维护每个点此时的根

我们定义find(x)为这个阶段x的根 （为啥定义的是find呢，因为寻根是并查集操作）

size(x)为这个阶段x的子树大小（节点个数）

A x y操作：

假设x 是y的父节点

我们把x到find(x)的每个点都加上size(y)即可

路径上加一个值，我们可以用树剖来维护

最后再并查集merge一下(x,y)

Q x y操作：

假设x是y的父节点

则答案就是(size(x) - size(y))*(size(y))

这里所要用到的询问，是区间加，单点询问，可以差分后维护树状数组

下面是代码，175ms，写这篇题解的在最优解排名在第一页rk6，应该还是比较快的

using namespace std;

#define MAXN 400005
#define lowbit(x) (x&(-x))
#define LL long long

int n,m;
int f[MAXN];

struct bian
{
    int x,y,ls;
}b[MAXN];
int t[MAXN],cnt;

struct aa
{
    bool opt;
    int x,y;
}p[MAXN];

void print(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
    putchar(x%10+'0');
}

inline int read()
{
    register int x = 0 , ch = getchar();
    while( !isdigit( ch ) ) ch = getchar();
    while( isdigit( ch ) ) x = x * 10 + ch - '0' , ch = getchar();
    return x;
}

void jb(int x,int y)//建边
{
    cnt ++;
    b[cnt].x = x;
    b[cnt].y = y;
    b[cnt].ls = t[x];
    t[x] = cnt;
}

void rd()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i ++)
    {
        char ch = 0;
        while(ch != 'A' && ch != 'Q') ch = getchar();

        if(ch == 'A') p[i].opt = 1;
        else p[i].opt = 0;

        p[i].x = read();
        p[i].y = read();
        if(p[i].opt == 1)
        {
            jb(p[i].x,p[i].y);
            jb(p[i].y,p[i].x);
        }   
    }
}

void csh(){//并查集初始化
    for(int i = 1; i <= n; i ++) f[i] = i; 
}

int find(int x)
{
    if(f[x] == x) return x;
    return f[x] = find(f[x]);
}

void mg(int x,int y)//mg就是merge
{
    f[find(y)] = find(x);
}

int c[MAXN];

void jia(int x,int y) {
    for(; x <= n; x += lowbit(x))
        c[x] += y;
}

int he(int x)
{
    int ans = 0;
    for(; x > 0; x -= lowbit(x))
        ans += c[x];
    return ans;
}

int ht[MAXN],th[MAXN],z[MAXN],s[MAXN],a[MAXN];
int fa[MAXN];

void dfs(int x)
{
    s[x] = 1;
    int mz = 0;
    for(int i = t[x]; i != 0; i = b[i].ls)
    {
        int y = b[i].y;
        if(y != fa[x]) {
            fa[y] = x;
            dfs(y);
            s[x] += s[y];
            if(s[y] > mz) 
            {
                mz = s[y];
                z[x] = y;
            }
        }
    }
}

void dfs2(int x,int _ht,int _th)
{
    ht[x] = _ht;
    th[x] = _th;

    cnt ++;
    a[x] = cnt;
    if(z[x])
    {
        dfs2(z[x],_ht,_th);
    }
    for(int i = t[x]; i != 0 ; i = b[i].ls)
    {
        int y = b[i].y;
        if(y != fa[x] && y != z[x]) {
            dfs2(y,y,_th+1);
        }
    }
}

void optA(int x,int y,int s)//x到y每个点点权+s
{
    while(ht[x] != ht[y])
    {
        jia(a[ht[x]],s);
        jia(a[x]+1,-s);
        x = fa[ht[x]];
    }
    jia(a[y],s);
    jia(a[x]+1,-s);
}

signed main()
{
    rd();
    csh();
    for(int i = 1; i <= m; i ++) {
        if(p[i].opt == 1) {
            mg(p[i].x,p[i].y);
        }
    }
    for(int i = 1; i <= n; i ++)
    {
        if(find(i) == i) {
            jb(i,n+1);
            jb(n+1,i);
        }
    }
    n ++;
    csh();
    dfs(n);
    cnt = 0;
    dfs2(n,n+1,1);
    jia(1,1);
    for(int i = 1; i <= m; i ++)
    {
        int x = p[i].x,y = p[i].y;
        if(fa[x] == y) swap(x,y);//确保y的父亲是x

        if(p[i].opt == 1)
        {
            optA(x,find(x),he(a[y]));
            mg(x,y);
        } else {
            LL ans = 0;
            int sa = he(a[find(x)]),sb = he(a[y]);
            ans = 1ll*(sa-sb)*sb;
            print(ans);
            puts("");
        }
    }

    return 0;
}

树链剖分写树链剖分，我　写　我　自　己