【kruskal重构树，倍增】2021 ICPC Asia Shanghai - H. Life is a Game
题目链接：Problem - H - Codeforces --- 问题 - H - Codeforces
题解
由于边权会对两个点的连通性造成影响，所以会想到可以按边权从小到大生成kruskal重构树，然后我们会发现，在重构树上一点u，只要满足 \(u的子树的点权和 + k ≥ u的父亲表示的边的边权\) 就能从u走到u的父亲，并且获得u的父亲的子树的点权和。
所以解题方向就很明显了，给定一个点x和自带能力值k，只要判断他最多能往上跳到哪个祖先，就能获得答案。
但因为kruskal重构树的深度可达n，所以不能一个一个往上跳，需要用倍增从大到小依次检验，然后跳，然后检验，然后跳，直到再也跳不动为止既是答案。
代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
struct DSU {
vector<int> f, siz;
DSU(int n) : f(n), siz(n, 1) { iota(f.begin(), f.end(), 0); }
int find(int x) {
while (x != f[x]) x = f[x] = f[f[x]];
return x;
}
bool same(int x, int y) { return find(x) == find(y); }
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
siz[x] += siz[y];
f[y] = x;
return true;
}
int size(int x) { return siz[find(x)]; }
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<array<int, 3>> e(m);
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
u--, v--;
e[i] = {w, u, v};
}
sort(e.begin(), e.end());
DSU dsu(n + m);
int cur = n;
vector<int> pa(n + m, -1), id(n + m);
vector<array<int, 2>> ch(n + m, {-1, -1});
for (int i = 0; i < m; i++) {
auto [w, u, v] = e[i];
u = dsu.find(u), v = dsu.find(v);
if (u == v) continue;
ch[cur] = {u, v};
pa[u] = cur, pa[v] = cur;
dsu.merge(cur, u);
dsu.merge(cur, v);
id[cur] = i;
cur++;
}
vector to(n + m, vector<int>(__lg(n + m) + 1, -1));
vector<int> sum(n + m);
auto dfs = [&](auto self, int u) -> void {
to[u][0] = pa[u];
for (int i = 1; i <= __lg(n + m); i++) {
if (to[u][i - 1] == -1) break;
to[u][i] = to[to[u][i - 1]][i - 1];
}
if (u < n) {
sum[u] = a[u];
return;
}
for (auto v : ch[u]) {
self(self, v);
sum[u] += sum[v];
}
};
dfs(dfs, cur - 1);
while (q--) {
int x, k;
cin >> x >> k;
x--;
int ans = a[x] + k;
while (true) {
int nxt = -1;
for (int i = __lg(n + m); i >= 0; i--) {
int p = to[x][i];
if (p != -1 && ans >= e[id[p]][0]) {
nxt = p;
break;
}
}
if (nxt == -1) break;
x = nxt;
ans = sum[x] + k;
}
cout << ans << '\n';
}
return 0;
}