【LCT】[COI2009] OTOCI

题目

不久之前，Mirko 建立了一个旅行社，名叫“极地之梦”。这家旅行社在北极附近购买了 nn 座冰岛，并且提供观光服务。

当地最受欢迎的当然是帝企鹅了，这些小家伙经常成群结队的游走在各个冰岛之间。Mirko 的旅行社遭受一次重大打击，以至于观光游轮已经不划算了。旅行社将在冰岛之间建造大桥，并用观光巴士来运载游客。

Mirko 希望开发一个电脑程序来管理这些大桥的建造过程，以免有不可预料的错误发生。这些冰岛从1到N标号。一开始时这些岛屿没有大桥连接，并且所有岛上的帝企鹅数量都是知道的。每座岛上的企鹅数量虽然会有所改变，但是始终在 [0, 1000][0,1000] 之间。你的程序需要处理以下三种命令：

bridge u v：询问结点 uu 与结点 vv 是否连通。如果是则输出 no；否则输出 yes，并且在结点 uu 和结点 vv 之间连一条无向边。
penguins u x：将结点 uu 对应的权值 w_uw
u
​
修改为 xx。
excursion u v：如果结点 uu 和结点 vv 不连通，则输出 impossible。否则输出结点 uu 到结点 vv 的路径上的点对应的权值的和。

思路

就是LCT板子题，维护一下splay的点权和即可

代码

#include<bits/stdc++.h>
using namespace std;
int fa[N],ch[N][2],v[N],tot[N],n,q,A,B,tem;
bool lazy[N];
char cha[101];
bool son(int x){return ch[fa[x]][1]==x;}
bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
void pushup(int x){tot[x]=tot[ch[x][0]]+tot[ch[x][1]]+v[x];}
void spread(int x)
{
    if(!lazy[x])return;
    tem=ch[x][0];
    ch[x][0]=ch[x][1];
    ch[x][1]=tem;
    lazy[ch[x][0]]^=1;
    lazy[ch[x][1]]^=1;
    lazy[x]=0;
}
void rotate(int x){
    if(!x||!fa[x]||isroot(x))return;
    int faz=fa[x],fazz=fa[faz],g=son(x);
    fa[x]=fazz;
    if(!isroot(faz))ch[fazz][son(faz)]=x;
    fa[ch[x][!g]]=faz;
    ch[faz][g]=ch[x][!g];
    fa[faz]=x;
    ch[x][!g]=faz;
    pushup(faz);
    pushup(x);
}
void clean(int x){
    if(!isroot(x))clean(fa[x]);
    spread(x);
}
void splay(int node)
{
    clean(node);
    while(!isroot(node)){
        if(!isroot(fa[node]))
            if(son(fa[node])^son(node))rotate(node);
            else rotate(fa[node]);
        rotate(node);
    }
    pushup(node);
}
void access(int x){
    for(int y=0;x;y=x,x=fa[x])
        splay(x),ch[x][1]=y,pushup(x);
}
void mroot(int x){
    access(x);
    splay(x);
    lazy[x]^=1;
}
void split(int x,int y){
    mroot(x);
    access(y);
    splay(y);
}
void link(int x,int y){
    mroot(x);
    fa[x]=y;
}
int findroot(int x)
{
    access(x);
    splay(x);
    while(ch[x][0])x=ch[x][0];
    return x;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",v+i),tot[i]=v[i];
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
	{
        scanf("%s%d%d",cha,&A,&B);
        if(cha[0]=='b')
		{
            if(findroot(A)==findroot(B))puts("no");
            else
			{
                puts("yes");
                link(A,B);
            }
        }
        else if(cha[0]=='p')access(A),splay(A),v[A]=B,pushup(A);
        else if(cha[0]=='e')
		{
            if(findroot(A)!=findroot(B))
			{
                puts("impossible");
                continue;
            }
            split(A,B);
            printf("%d\n",tot[B]);
        }
    }
}