lupgu P3950 部落冲突

题目链接

luogu P3950 部落冲突

题解

树剖线段树可以

lct还行

代码

#include<cstdio>

#include<algorithm>

inline int read() {

    int x = 0,f = 1;

    char c = getchar();

    while(c < '0' || c > '9')c = getchar();

    while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();

    return x * f;

}

const int maxn = 300007;

int ch[maxn][2],rev[maxn],fa[maxn];

bool isroot(int x) { return ch[fa[x]][1] != x && ch[fa[x]][0] != x;}

void pushdown(int x) {

    if(rev[x]) {rev[x] ^= 1,std::swap(ch[x][1],ch[x][0]),rev[ch[x][1]] ^= 1,rev[ch[x][0]] ^= 1;}

}

void rotate(int x) {

    int y = fa[x],z = fa[y],d = (ch[y][1] == x) ^ 1;

    if(!isroot(y)) ch[z][ch[z][1] == y] = x;

    fa[x] = z;

    ch[y][d ^ 1] = ch[x][d]; fa[ch[x][d]] = y;

    ch[x][d] = y; fa[y] = x;

}

int stack[maxn],top = 0;

void splay(int x) {

    stack[++ top] = x;

    for(int i = x;!isroot(i);i = fa[i]) stack[++ top] = fa[i];

    while(top) pushdown( stack[top --]);

    while(!isroot(x)) {

        int y = fa[x],z = fa[y];

        if(!isroot(y)) {

            if((ch[y][1] == x) ^ (ch[z][1] == y)) rotate(x);

            else rotate(y);

        } rotate(x);

    }

}

void access(int x) {

    for(int i = 0;x;i = x , x = fa[x])

        splay(x), ch[x][1] = i;

}

void makeroot(int x) {access(x),splay(x),rev[x] ^= 1; }

void link(int x,int y) { makeroot(x),fa[x] = y;return splay(x); }

void cut(int x,int y) {makeroot(x),access(y),splay(y),ch[y][0] = fa[x] = 0;}

int find(int x) {

    for(access(x),splay(x);ch[x][0];x = ch[x][0]) ;

        return x;

}

int p1[maxn],p2[maxn],num = 0;

int main() {

    int n,m;

    n = read(),m = read();

    for(int a,b,i = 1;i < n;++ i) a = read(),b = read(),link(a,b);

    char s[10];

    while(m -- ) {

        int a,b;

        scanf("%s",s + 1);

        if(s[1] == 'U') {a = read(), link(p1[a],p2[a]);}

        else if(s[1] == 'C') {a = read(),b = read();++ num,cut(p1[num] = a,p2[num] = b);}

        else {a = read(),b = read();puts(find(a) == find(b) ? "Yes" : "No"); }

    }

    return 0;

}