「ZJOI2015」幻想乡战略游戏

发表于
https://loj.ac/problem/2135

题目链接

「ZJOI2015」幻想乡战略游戏

做法

原问题实则为动态求带权重心问题。设每个点的花费为 $ W_i $ ， 从任意非带权重心一点出发，每次向相邻的点中 $ W_v $ 最小的走，最后会走到带权重心。
如果已知 $ W_u $ ，求 $ u $ 的子节点 $ v $ 的 $ W_v $ 。设 $ len(u, v) $ 为 $ u, v $ 间的距离， $ cnt_u $ 为 $ u $ 子树内的军队单位数，则 $ W_v = W_u + len(u, v)(cnt_u - cnt_v \times 2) $ 。
考虑用点分治加速计算 $ W_u $ 并加速求解。每次向点分树子节点中存在比当前分治重心更优秀的点的子树跳，跳的过程复杂度 $ O(q \log n) $ 。
每次每个节点求 $ W_u $ 时间为 $ O(\log n) $ ，总时间复杂度为 $ O(n \log n + q \log^2 n) $ 。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int N = 200010;
int n, m, lg[N];
vector<pii> e[N], E[N];
int dfn[N], dep[N], idx = 0, st[18][N]; ll Dep[N];
int sz[N], mx[N], root, size, rt;
bool vis[N]; int fa[N];
int id[N]; ll sum[N], cnt[N];
ll dn[N], up[N];

inline int LCA(int x, int y) {
	x = dfn[x], y = dfn[y]; if(x > y) swap(x, y); int k = y - x + 1;
	return dep[st[lg[k]][x]] <= dep[st[lg[k]][y - (1 << lg[k]) + 1]] ? st[lg[k]][x] : st[lg[k]][y - (1 << lg[k]) + 1];
}
inline ll Dis(int x, int y) { return Dep[x] + Dep[y] - Dep[LCA(x, y)] * 2; }
void dfs1(int u, int ff) {
	dep[u] = dep[ff] + 1, dfn[u] = ++idx, st[0][idx] = u;
	for(auto v : e[u]) if(v.fst != ff) Dep[v.fst] = Dep[u] + v.snd, dfs1(v.fst, u), st[0][++idx] = u;
}
void getrt(int u, int ff) {
	sz[u] = 1, mx[u] = 0;
	for(auto v : e[u]) if(v.fst != ff && !vis[v.fst])
		getrt(v.fst, u), sz[u] += sz[v.fst], mx[u] = max(mx[u], sz[v.fst]);
	mx[u] = max(mx[u], size - sz[u]); if(mx[u] < mx[root]) root = u;
}
void build(int u) {
	getrt(u, 0), vis[u] = 1;
	for(auto v : e[u]) if(!vis[v.fst]) {
		mx[root = 0] = size = sz[v.fst], getrt(v.fst, 0);
		E[u].pb(mp(root, v.fst)), fa[root] = u, build(root);
	}
}
void init() {
	dfs1(1, 0), lg[0] = -1; rep(i, 1, idx) lg[i] = lg[i >> 1] + 1;
	rep(j, 1, 17)
		rep(i, 1, idx - (1 << j) + 1)
			st[j][i] = dep[st[j - 1][i]] <= dep[st[j - 1][i + (1 << j - 1)]] ? st[j - 1][i] : st[j - 1][i + (1 << j - 1)];
	mx[root = 0] = size = n, getrt(1, 0), rt = root, build(root);
}
void mdy(int x, int w) {
	cnt[x] += w;
	for(int i = x; fa[i]; i = fa[i]) {
		ll dis = Dis(fa[i], x); dn[fa[i]] += dis * w, up[i] += dis * w, cnt[fa[i]] += w;
	}
}
ll calc(int x) {
	ll res = dn[x];
	for(int i = x; fa[i]; i = fa[i]) {
		ll dis = Dis(fa[i], x); res += dn[fa[i]] - up[i] + dis * (cnt[fa[i]] - cnt[i]);
	}
	return res;
}
ll qry(int x) {
	ll res = calc(x);
	for(auto v : E[x]) if(calc(v.snd) < res) return qry(v.fst);
	return res;
}
int main() {
	scanf("%d%d", &n, &m);
	rep(i, 2, n) { int x, y, z; scanf("%d%d%d", &x, &y, &z), e[x].pb(mp(y, z)), e[y].pb(mp(x, z)); }
	init();
	for(int x, y; m; --m) scanf("%d%d", &x, &y), mdy(x, y), printf("%lld\n", qry(rt));
	return 0;
}