Luogu

BZOJ

分析

LCT板子题。

判断连通性的话,可以用$\mathrm{findroot}$。

然后每个点维护一个$\mathrm{sum}$就行了。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=30010;

struct Link_Cut_Tree {
    int fa[N],ch[N][2],v[N],sum[N],rev[N];
    int sta[N];
    inline int nroot(int x) { return ch[fa[x]][0]==x||ch[fa[x]][1]==x; }
    inline void pushup(int x) { sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+v[x]; }
    inline void reverse(int x) { swap(ch[x][0],ch[x][1]); rev[x]^=1; }
    inline void pushdown(int x) {
        if (rev[x]) {
            if (ch[x][0]) reverse(ch[x][0]);
            if (ch[x][1]) reverse(ch[x][1]);
            rev[x]=0;
        }
    }
    inline void rotate(int x) {
        int y=fa[x],z=fa[y],k=(x==ch[y][1]),w=ch[x][!k];
        if (nroot(y)) ch[z][ch[z][1]==y]=x;
        ch[x][!k]=y,ch[y][k]=w;
        if (w) fa[w]=y; fa[y]=x,fa[x]=z;
        pushup(y);
    }
    inline void splay(int x) {
        int y=x,z=0; sta[++z]=y;
        while (nroot(y)) sta[++z]=y=fa[y];
        while (z) pushdown(sta[z--]);
        while (nroot(x)) {
            y=fa[x],z=fa[y];
            if (nroot(y)) rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
            rotate(x);
        }
        pushup(x);
    }
    inline void access(int x) {
        for (re int y=0;x;x=fa[y=x]) splay(x),ch[x][1]=y,pushup(x);
    }
    inline void makeroot(int x) { access(x); splay(x); reverse(x); }
    inline int findroot(int x) {
        access(x); splay(x);
        while (ch[x][0]) pushdown(x),x=ch[x][0];
        return x;
    }
    inline void split(int x,int y) { makeroot(x); access(y); splay(y); }
    inline void link(int x,int y) { makeroot(x); fa[x]=y; }
} T;

int main() {
    int n=read();
    for (re int i=1;i<=n;++i) T.v[i]=read();
    int m=read();
    while (m--) {
        char op[10]; scanf("%s",op);
        int x=read(),y=read();
        if (op[0]=='b') {
            if (T.findroot(x)==T.findroot(y)) puts("no");
            else puts("yes"),T.link(x,y);
        }
        else if (op[0]=='p') T.splay(x),T.v[x]=y;
        else if (op[0]=='e') {
            if (T.findroot(x)!=T.findroot(y)) puts("impossible");
            else T.split(x,y),printf("%d\n",T.sum[y]);
        }
    }
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 19 PM