一大早上到机房想先拍一下模板，热热身.
结果....对照着染色敲的 LCT 竟然死活也调不过去（你说我抄都能抄错）
干脆自己重新敲了一遍，10min就敲完了.......
还是要相信自己
Code:
#include <bits/stdc++.h>
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
#define maxn 40000
struct LCT
{
#define lson ch[x][0]
#define rson ch[x][1]
int tag[maxn],val[maxn],sumv[maxn],ch[maxn][2],f[maxn],sta[maxn];
int isRoot(int x)
{
return !(ch[f[x]][1] == x || ch[f[x]][0] == x);
}
int get(int x)
{
return ch[f[x]][1] == x;
}
void mark(int x)
{
if(!x) return ;
swap(lson, rson), tag[x] ^= 1;
}
void pushdown(int x)
{
if(!x) return ;
if(tag[x])
{
mark(lson), mark(rson), tag[x] ^=1 ;
}
}
void pushup(int x)
{
sumv[x] = sumv[lson] + sumv[rson] + val[x];
}
void rotate(int x)
{
int old = f[x], fold = f[old], which = get(x);
if(!isRoot(old)) ch[fold][ch[fold][1] == old] = x;
ch[old][which] = ch[x][which ^ 1], f[ch[old][which]] = old;
ch[x][which ^ 1 ] = old, f[old] = x, f[x] = fold;
pushup(old),pushup(x);
}
void splay(int x)
{
int u = x, v = 0;
sta[++v] = u;
while(!isRoot(u)) sta[++v] = f[u], u = f[u];
while(v) pushdown(sta[v--]);
u = f[u];
for(int fa; (fa = f[x]) != u; rotate(x))
if(f[fa] != u) rotate(get(fa) == get(x) ? fa: x);
}
void Access(int x)
{
for(int y = 0; x ; y = x,x = f[x])
{
splay(x), rson = y, pushup(x);
}
}
void makeRoot(int x)
{
Access(x), splay(x), mark(x);
}
void link(int a,int b)
{
makeRoot(a), f[a] = b;
}
void split(int a,int b)
{
makeRoot(a), Access(b), splay(b);
}
}T;
struct Union_Find
{
int p[maxn];
void init()
{
for(int i = 0;i < maxn ;++i) p[i] = i;
}
int find(int x)
{
return p[x] == x ? x : p[x] = find(p[x]);
}
int merge(int a,int b)
{
int x = find(a), y = find(b);
if(x == y) return 0;
p[x] = y;
return 1;
}
}U;
char str[20];
int main()
{
// setIO("input");
U.init();
int n;
scanf("%d",&n);
for(int i = 1;i <= n; ++i) scanf("%d",&T.val[i]), T.sumv[i] = T.val[i];
int q,a,b,c;
scanf("%d",&q);
while(q --)
{
scanf("%s",str);
if(str[0] == 'b')
{
scanf("%d%d",&a,&b);
if(!U.merge(a,b))
printf("no\n");
else
{
T.link(a, b);
printf("yes\n");
}
}
if(str[0] == 'p' )
{
scanf("%d%d",&a,&b);
T.makeRoot(a),T.val[a] = b, T.pushup(a);
}
if(str[0] == 'e')
{
scanf("%d%d",&a,&b);
if(U.find(a) == U.find(b))
{
T.split(a,b);
printf("%d\n",T.sumv[b]);
}else printf("impossible\n");
}
}
return 0;
}