题目描述
不久之前，Mirko建立了一个旅行社，名叫“极地之梦”。这家旅行社在北极附近购买了 N 座冰岛，并且提供观光服务。当地最受欢迎的当然是帝企鹅了，这些小家伙经常成群结队的游走在各个冰岛之间。
Mirko的旅行社遭受一次重大打击，以至于观光游轮已经不划算了。旅行社将在冰岛之间建造大桥，并用观光巴士来运载游客。Mirko希望开发一个电脑程序来管理这些大桥的建造过程，以免有不可预料的错误发生。
这些冰岛从 1 到 N 标号。一开始时这些岛屿没有大桥连接，并且所有岛上的帝企鹅数量都是知道的。每座岛上的企鹅数量虽然会有所改变，但是始终在 [0,1000] 之间。
你的程序需要处理以下三种命令：
bridge A B ：在 A 与 B 之间建立一座大桥（A 与 B 是不同的岛屿）。由于经费限制，这项命令被接受，当且仅当 A 与 B 不联通。若这项命令被接受，你的程序需要输出yes，之后会建造这座大桥。否则，你的程序需要输出no。
penguins A X ：根据可靠消息，岛屿 A此时的帝企鹅数量变为 X。这项命令只是用来提供信息的，你的程序不需要回应。
excursion A B ：一个旅行团希望从 A 出发到 B。若 A 与 B 连通，你的程序需要输出这个旅行团一路上所能看到的帝企鹅数量（包括起点 A 与终点 B ），若不联通，你的程序需要输出impossible。
输入格式
第一行一个正整数 N ，表示冰岛的数量。
第二行 N 个范围 [0,1000] 的整数，为每座岛屿初始的帝企鹅数量。
第三行一个正整数 M ，表示命令的数量。
接下来 M 行即命令，为题目描述所示。
输出格式
对于每个bridge命令与excursion命令，输出一行，为题目描述所示。
一开始以为是LCT，然而我太弱以至于根本不会LCT，DJY提醒我只要树剖就可以了，强行被报标算，不A都对不起良心了。对于bridge只要用并查集判断即可，对于excursion在第一遍并查集的时候顺便记一下要不要输 impossible ，然后把森林连到虚点上变成一棵树，建出树后树剖一下，只要维护一下区间和即可。
#include<bits/stdc++.h> const int N = 3e4 + 10; const int M = 1e5 + 10; template <typename T> void read(T &x) { x = 0; char c = getchar(); for (; !isdigit(c); c = getchar()); for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; } int n, m, a[N], f[N], first[N], s; char op[10]; struct edge{ int y, next; }mp[N * 4]; void ins(int x, int y) { mp[++s] = (edge) {y, first[x]}; first[x] = s; mp[++s] = (edge) {x, first[y]}; first[y] = s; } int find(int x) { if (f[x] == x) return x; return f[x] = find(f[x]); } namespace force { int x, y; void bridge(int x, int y) { int f1 = find(x); int f2 = find(y); if (f1 == f2) {printf("no\n"); return;} printf("yes\n"); f[f1] = f2; ins(x, y); } bool dfs(int x, int y, int sum, int last) { if (x == y) {printf("%d\n", sum); return 1;} for (int t=first[x]; t; t=mp[t].next) if (mp[t].y != last && dfs(mp[t].y, y, sum + a[mp[t].y], x)) return 1; return 0; } int main() { read(n); for (int i=1; i <= n; i++) read(a[i]), f[i] = i; read(m); while (m--) { scanf("%s", op); read(x); read(y); if (op[0] == 'b') bridge(x, y); if (op[0] == 'p') a[x] = y; if (op[0] == 'e') if (!dfs(x, y, a[x], -1)) printf("impossible\n"); } return 0; } } namespace try_it { int x[M], y[M]; char opt[M]; int fa[N][20], size[N], top[N], dep[N], pos[N], cnt; int lc[N * 4], rc[N * 4], sum[N * 4], node; bool z[M], vis[N]; bool bridge(int x, int y) { int f1 = find(x); int f2 = find(y); if (f1 == f2) return 0; f[f1] = f2; ins(x, y); return 1; } void dfs1(int x) { vis[x] = 1; for (int t=first[x]; t; t=mp[t].next) if (!vis[mp[t].y]) dfs1(mp[t].y); } int dfs2(int x) { for (int i=1; dep[x] - (1 << i) >= 0; i++) fa[x][i] = fa[fa[x][i - 1]][i - 1]; size[x] = 1; for (int t=first[x]; t; t=mp[t].next) if (mp[t].y != fa[x][0]) fa[mp[t].y][0] = x, dep[mp[t].y] = dep[x] + 1, size[x] += dfs2(mp[t].y); return size[x]; } void dfs3(int x, int cap) { top[x] = cap; pos[x] = ++cnt; int mxszi = 0; for (int t=first[x]; t; t=mp[t].next) if (mp[t].y != fa[x][0] && size[mp[t].y] > size[mxszi]) mxszi = mp[t].y; if (!mxszi) return; dfs3(mxszi, cap); for (int t=first[x]; t; t=mp[t].next) if (mp[t].y != fa[x][0] && mp[t].y != mxszi) dfs3(mp[t].y, mp[t].y); } void build(int i, int l, int r) { if (l == r) return; lc[i] = ++node; build(lc[i], l, (l + r) / 2); rc[i] = ++node; build(rc[i], (l + r) / 2 + 1, r); } void chg(int i, int l, int r, int x, int c) { if (l == r) {sum[i] = c; return;} if (x <= (l + r) / 2) chg(lc[i], l, (l + r) / 2, x, c); else chg(rc[i], (l + r) / 2 + 1, r, x, c); sum[i] = sum[lc[i]] + sum[rc[i]]; } int lca(int x, int y) { if (dep[x] < dep[y]) std::swap(x, y); for (int i=19; i >= 0; i--) if (dep[x] - (1 << i) >= dep[y]) x = fa[x][i]; for (int i=19; i >= 0; i--) if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i]; if (x == y) return x; return fa[x][0]; } int qry(int i, int l, int r, int _l, int _r) { if (l > _r || r < _l) return 0; if (l >= _l && r <= _r) return sum[i]; return qry(lc[i], l, (l + r) / 2, _l, _r) + qry(rc[i], (l + r) / 2 + 1, r, _l, _r); } int qry(int x, int y) { int l = lca(x, y), ret = - a[l]; while (dep[top[x]] > dep[l]) ret += qry(1, 1, cnt, pos[top[x]], pos[x]), x = fa[top[x]][0]; ret += qry(1, 1, cnt, pos[l], pos[x]); while (dep[top[y]] > dep[l]) ret += qry(1, 1, cnt, pos[top[y]], pos[y]), y = fa[top[y]][0]; ret += qry(1, 1, cnt, pos[l], pos[y]); return ret; } int main() { read(n); for (int i=1; i <= n; i++) read(a[i]), f[i] = i; read(m); for (int i=1; i <= m; i++) { scanf("%s", op); opt[i] = op[0]; read(x[i]); read(y[i]); if (opt[i] == 'b') z[i] = bridge(x[i], y[i]); if (opt[i] == 'e') z[i] = find(x[i]) == find(y[i]); } for (int i=1; i <= n; i++) if (!vis[i]) dfs1(i), ins(n + 1, i); dfs2(n + 1); dfs3(n + 1, n + 1); node = 1; build(1, 1, cnt); for (int i=1; i <= n; i++) chg(1, 1, cnt, pos[i], a[i]); for (int i=1; i <= m; i++) { if (opt[i] == 'b') if (z[i]) printf("yes\n"); else printf("no\n"); else; if (opt[i] == 'p') chg(1, 1, cnt, pos[x[i]], y[i]), a[x[i]] = y[i]; if (opt[i] == 'e') if (z[i]) printf("%d\n", qry(x[i], y[i])); else printf("impossible\n"); else; } return 0; } } int main() { //force::main(); try_it::main(); return 0; }