欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[Luogu P4219] [BJOI2014]大融合

程序员文章站 2024-03-17 20:21:40
...

题目描述

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

[Luogu P4219] [BJOI2014]大融合

例如,在上图中,现在一共有了 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 表示在xy 之间连一条边。保证之前 xy 是不联通的。
Q x y表示询问 (x,y) 这条边上的负载。保证 xy 之间有一条边。

输入输出样例

输入样例#1:

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

输出样例#1:

6

解题分析

显然答案是x子树和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的虚儿子个数也为其子树大小
        }
    }
}
相关标签: LCT