[COCI 2009] OTOCI / 极地旅行社

LCT

传送门

洛谷
BZOJ

Solution

随便写吧,就是一道裸的LCT模板

代码实现

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
using namespace std;
#define ll long long
#define re register
#define file(a) freopen(a".in",,"r",stdin);freopen(a".out","w",stdout)
inline int gi()
{
    int f=1,sum=0;char ch=getchar();
    while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
    return f*sum;
}
const int N=500010;
struct node
{
    int val,ff,sum,rev,ch[2];
}t[N<<1];
int top,sta[N];
void pushup(int x){t[x].sum=t[t[x].ch[0]].sum+t[t[x].ch[1]].sum+t[x].val;}
void reverse(int o){t[o].rev^=1;swap(t[o].ch[0],t[o].ch[1]);}
void pushdown(int o){if(!t[o].rev)return;if(t[o].ch[0])reverse(t[o].ch[0]);if(t[o].ch[1])reverse(t[o].ch[1]);t[o].rev^=1;}
bool isroot(int o){return (t[t[o].ff].ch[0]!=o) && (t[t[o].ff].ch[1]!=o);}
void rotate(int x){int y=t[x].ff,z=t[y].ff;if(!isroot(y)){t[z].ch[t[z].ch[1]==y]=x;}t[x].ff=z;int k=t[y].ch[1]==x;t[y].ch[k]=t[x].ch[k^1];t[t[x].ch[k^1]].ff=y;t[x].ch[k^1]=y;t[y].ff=x;pushup(y);}
void splay(int x){sta[++top]=x;for(int pos=x;!isroot(pos);pos=t[pos].ff)sta[++top]=t[pos].ff;while(top)pushdown(sta[top--]);while(!isroot(x)){int y=t[x].ff,z=t[y].ff;if(!isroot(y))(t[y].ch[0]==x)^(t[z].ch[0]==y)?rotate(x):rotate(y);rotate(x);}pushup(x);}
void access(int x){for(int y=0;x;y=x,x=t[x].ff)splay(x),t[x].ch[1]=y,pushup(x);}
void makeroot(int x){access(x);splay(x);reverse(x);}
int findroot(int x){access(x);splay(x);while(t[x].ch[0])x=t[x].ch[0];return x;}
void split(int x,int y){makeroot(x);access(y);splay(y);}
void link(int x,int y){makeroot(x);t[x].ff=y;}
void cut(int x,int y){split(x,y);t[x].ff=t[y].ch[0]=0;}
int n,m;char s[110];
int main()
{
    n=gi();
    for(int i=1;i<=n;i++)t[i].val=t[i].sum=gi();
    int Q=gi();
    while(Q--)
    {
        scanf("%s",s);int x=gi();
        if(s[0]=='b')
        {
            int b=gi();
            if(findroot(x)==findroot(b))puts("no");
            else{puts("yes");link(x,b);}
        }
        if(s[0]=='p')
        {
            access(x);splay(x);
            t[x].val=gi();pushup(x);
        }
        if(s[0]=='e')
        {
            int y=gi();
            if(findroot(x)!=findroot(y))puts("impossible");
            else
            {
                split(x,y);printf("%d\n",t[y].sum);
            }
        }
    }
    return 0;
}