BZOJ 4530: [BJOI2014]大融合 – [LCT]


题目传送门(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 
#include 
#define ll long long
const 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]));
    }
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注