题目传送门(BZOJ)
>原文链接<

题解 :

有关LCT的讲解,请见本人给 OI-Wiki 的供稿 :LCT!

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define ls ch[p][0]#define rs ch[p][1]#define get(x) (ch[f[x]][1] == x)using namespace std;const int N = 31000;int ch[N][2], f[N], sum[N], tag[N], val[N];#define isRoot(p) (ch[f[p]][0] != p && ch[f[p]][1] != p)inline void pd(int p) { if(tag[p]) { swap(ch[ls][0], ch[ls][1]); swap(ch[rs][0], ch[rs][1]); tag[ls] ^= 1, tag[rs] ^= 1; tag[p] = 0; }}void Up(int p) { if(!isRoot(p)) Up(f[p]); pd(p);}inline void pu(int p) { sum[p] = sum[ls] + sum[rs] + val[p];}inline void Rotate(int x) { int y = f[x], z = f[y], k = get(x); if(!isRoot(y)) ch[z][ch[z][1] == y] = x; ch[y][k] = ch[x][!k], f[ch[y][k]] = y; ch[x][!k] = y, f[y] = x, f[x] = z; pu(y), pu(x);}void Splay(int p) { Up(p); for(int fa; fa = f[p], !isRoot(p); Rotate(p)) if(!isRoot(fa)) Rotate(get(p) == get(fa) ? fa : p);}void Access(int p) { for(int t = 0; p; t = p, p = f[p]) { Splay(p), ch[p][1] = t, pu(p); }}inline void MakeRoot(int p) { Access(p); Splay(p), swap(ls, rs); tag[p] ^= 1;}inline void Link(int x, int p) { MakeRoot(x), f[x] = p, Splay(x);}int find(int p) { Access(p), Splay(p); while(ls) pd(p), p = ls; return p;}int main() { int n, m; scanf("%d", &n); for(int i=1;i<=n;i++) scanf("%d", &val[i]); scanf("%d", &m); while(m--) { char opt[20]; int x, p; scanf("%s%d%d", opt, &x, &p); if(opt[0]=='b') { int dx = find(x), dy = find(p); if(dx!=dy) { puts("yes");Link(x, p); } else { puts("no"); } } else if(opt[0]=='p'){ MakeRoot(x);Access(x);Splay(x); val[x]=sum[x]=p; } else { int dx = find(x), dy = find(p); if(dx!=dy) { puts("impossible"); } else { MakeRoot(x);Access(p);Splay(p); printf("%d\n", sum[p]); } } }}