题目大意：有$n(nleqslant3 imes10^4)$个点，每个点有点权，$m(mleqslant3 imes10^5)$个操作，操作分三种：
- $bridge;x;y：$询问节点$x$与节点$y$是否连通，若不连通则连一条边
- $penguins;x;y：$把节点$x$点权改为$y$
- $excursion;x;y：$询问$x->y$路径上点权和
题解：$LCT$直接维护即可
卡点：无
C++ Code：
#include <algorithm>
#include <cstdio>
#define maxn 30010
#define lc(rt) son[rt][0]
#define rc(rt) son[rt][1]
int son[maxn][2], fa[maxn], tg[maxn];
int w[maxn], S[maxn];
inline bool get(int rt, int tg = 1) { return son[fa[rt]][tg] == rt; }
inline bool is_root(int rt) { return !(get(rt, 0) || get(rt)); }
inline void update(int rt) {
S[rt] = S[lc(rt)] + S[rc(rt)] + w[rt];
}
inline void pushdown(int rt) {
if (tg[rt]) {
tg[rt] ^= 1, tg[lc(rt)] ^= 1, tg[rc(rt)] ^= 1;
std::swap(lc(rt), rc(rt));
}
}
inline void rotate(int x) {
int y = fa[x], z = fa[y], b = get(x);
if (!is_root(y)) son[z][get(y)] = x;
fa[son[y][b] = son[x][!b]] = y, son[x][!b] = y;
fa[y] = x, fa[x] = z;
update(y), update(x);
}
inline void splay(int x) {
static int S[maxn], top;
S[top = 1] = x;
for (int y = x; !is_root(y); S[++top] = y = fa[y]) ;
for (; top; top--) pushdown(S[top]);
for (; !is_root(x); rotate(x)) if (!is_root(fa[x]))
get(x) ^ get(fa[x]) ? rotate(x) : rotate(fa[x]);
update(x);
}
inline void access(int x) { for (int t = 0; x; rc(x) = t, t = x, x = fa[x]) splay(x); }
inline void make_root(int rt) { access(rt), splay(rt), tg[rt] ^= 1; }
inline void link(int x, int y) { make_root(x), fa[x] = y; }
inline void split(int x, int y) { make_root(x), access(y), splay(y); }
inline void cut(int x, int y) { split(x, y), lc(y) = fa[x] = 0; }
inline int findroot(int x) {
access(x), splay(x);
while (lc(x)) x = lc(x), pushdown(x);
splay(x);
return x;
}
inline bool connected(int x, int y) {
split(x, y);
return x == findroot(y);
}
int n, m;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", w + i);
S[i] = w[i];
}
scanf("%d", &m);
while (m --> 0) {
char op[15];
int x, y;
scanf("%s%d%d", op, &x, &y);
switch (*op) {
case 'b':
if (connected(x, y)) puts("no");
else {
puts("yes");
link(x, y);
}
break;
case 'p':
make_root(x);
w[x] = y;
update(x);
break;
case 'e':
if (connected(x, y)) {
split(x, y);
printf("%d
", S[y]);
} else puts("impossible");
}
}
return 0;
}