自动搬运

查看原文

来自洛谷，原作者为

	kai586123 啊嗯

搬运于2025-08-24 21:47:56，当前版本为作者最后更新于2019-07-29 20:26:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

其他题解都是动态点分治，这篇题解是用线段树+树剖的。

欢迎来我的Blog来看：[ZJOI2015] 幻想乡战略游戏

---

先上个复杂度吧：修改$O(nlog^2n)$，查询$O(nlogn)$，截止到发题解是最优解第二名

一个结论： 本题中，重心位置和点权，边权无关

看起来不可思议吧。

证明：

我们可以换一种方式计算答案。枚举边$edge_i$，这条边把树分为两部分。它的两端点是$x_i,y_i$，两子树的大小为$size_x,size_y$，那么有：

$$ans=\sum edge_i * size_x * size_y$$

通过直接构造出重心位置，并证明其它位置不比它更优证明结论：

在树上选一个点，使得它最大的子树大小（子树内军队数量）最小。这个点就是重心。

可以任选一个其它点，计算出以这个点为补给站的答案。考虑把选择的点向重心移动一条边对答案的影响。这条边是$edge$，两边为$x,y$，大小分别为$size_x,size_y$。从$x$走到$y$。

由推导出的新计算式，只有移动经过的这条边对答案产生的贡献发生了变化，是：

$$-edge * size_y + edge * size_x$$

显然，因为这个点不在我们选出的重心，$size_y$不可能小于$size_x$，即，让答案更优了。

实际上，这个点和普通不带权树的重心位置一样。

快速找到重心

在树上找到一个点$x$，满足$size_{root} \leq size_x * 2$，且$x$最深。

这个结合普通树重心性质很容易得出。

线段树叶子维护子树大小，其他节点维护线段树上子节点大小最大值。查询的时候在线段树上二分。

求答案

$$ans=\sum dis(x,y) * e(y)$$ $$=\sum (dis(x,root)+dis(y,root)-2* dis(lca,root)) * e(y) $$$$=\sum dis(x,root)* e(y) + \sum dis(y,root) * e(y) $$$$-2\sum dis(lca,root) * e(y)$$

前两个随便维护，重点是第三个。

令点权为$w_x=edge(x,fa(x))$，每次修改一个点的时候，就把它到根的大小$size$全部加上修改的值。查询重心到根，每个点$size_x * w_x$。

这是因为两个点到lca到根的路径，是两个点到根的共同路径。

#include <bits/stdc++.h>
typedef long long LL;

inline int rd() {
	int a = 1, b = 0; char c = getchar();
	while (!isdigit(c)) a = c == '-' ? 0 : 1, c = getchar();
	while (isdigit(c)) b = b * 10 + c - '0', c = getchar();
	return a ? b : -b;
}

const int N = 1e5 + 233;
int n, m;

struct Graph { int to, nxt, cost; } g[N * 2];
int head[N], tot;

inline void addedge(int x, int y, int c) {
	g[++tot].to = y, g[tot].nxt = head[x],
	g[tot].cost = c, head[x] = tot;
}

int fa[N], son[N], size[N], dep[N], dis[N];
int top[N], id[N], wh[N], wt[N], num;

void dfs1(int x) {
	for (int i = head[x]; i; i = g[i].nxt) {
		int y = g[i].to;
		if (y != fa[x]) {
			fa[y] = x; dep[y] = dep[x] + 1;
			dis[y] = dis[x] + g[i].cost;
			size[y] = 1;
			dfs1(y);
			if (size[son[x]] < size[y])
				son[x] = y;
			size[x] += size[y];
		}
	}
}

void dfs2(int x, int topf) {
	top[x] = topf; id[x] = ++num; wh[num] = x;
	wt[num] = dis[x] - dis[fa[x]];
	if (son[x]) {
		dfs2(son[x], topf);
		for (int i = head[x]; i; i = g[i].nxt) {
			int y = g[i].to;
			if (y != fa[x] && y != son[x])
				dfs2(y, y);
		}
	}
}

#define ls(p) p << 1
#define rs(p) p << 1 | 1

int sz[N * 4], tag[N * 4];
LL edge[N * 4], sum[N * 4];

void build(int p, int L, int R) {
	if (L == R) {
		edge[p] = wt[L];
		return;
	}
	int mid = (L + R) >> 1;
	build(ls(p), L, mid);
	build(rs(p), mid + 1, R);
	edge[p] = edge[ls(p)] + edge[rs(p)];
}

inline void pushup(int p) {
	sz[p] = std::max(sz[ls(p)], sz[rs(p)]);
	sum[p] = sum[ls(p)] + sum[rs(p)];
}

inline void pushdown(int p) {
	if (tag[p]) {
		sz[ls(p)] += tag[p];
		sz[rs(p)] += tag[p];
		tag[ls(p)] += tag[p];
		tag[rs(p)] += tag[p];
		sum[ls(p)] += (LL)tag[p] * edge[ls(p)];
		sum[rs(p)] += (LL)tag[p] * edge[rs(p)];
		tag[p] = 0;
	}
}

void add(int p, int l, int r, int v, int L, int R) {
	if (l <= L && r >= R) {
		sz[p] += v; tag[p] += v;
		sum[p] += (LL)v * edge[p];
		return;
	}
	pushdown(p);
	int mid = (L + R) >> 1;
	if (l <= mid)
		add(ls(p), l, r, v, L, mid);
	if (r > mid)
		add(rs(p), l, r, v, mid + 1, R);
	pushup(p);
}

LL query(int p, int l, int r, int L, int R) {
	if (l <= L && r >= R)
		return sum[p];
	pushdown(p);
	int mid = (L + R) >> 1;
	LL ret = 0;
	if (l <= mid)
		ret += query(ls(p), l, r, L, mid);
	if (r > mid)
		ret += query(rs(p), l, r, mid + 1, R);
	return ret;
}

inline int weight() {
	int p = 1, L = 1, R = n;
	while (L < R) {
		pushdown(p);
		int mid = (L + R) >> 1;
		if (sz[rs(p)] * 2 >= sz[1])
			L = mid + 1, p = rs(p);
		else R = mid, p = ls(p);
	}
	return wh[L];
}

inline void range_add(int x, int y) {
	while (top[x] != 1) {
		add(1, id[top[x]], id[x], y, 1, n);
		x = fa[top[x]];
	}
	add(1, 1, id[x], y, 1, n);
}

inline LL range_query(int x) {
	LL ret = 0;
	while (top[x] != 1) {
		ret += query(1, id[top[x]], id[x], 1, n);
		x = fa[top[x]];
	}
	return ret + query(1, 1, id[x], 1, n);
}

LL sum_dis_e, sum_e;

inline LL getans(int x) {
	return sum_dis_e + dis[x] * sum_e - 2 * range_query(x);
}

int main() {
	n = rd(); m = rd();
	for (int i = 1; i < n; ++i) {
		int x = rd(), y = rd(), c = rd();
		addedge(x, y, c);
		addedge(y, x, c);
	}
	
	dfs1(1); dfs2(1, 1);
	build(1, 1, n);
	
	while (m--) {
		int x = rd(), y = rd();
		sum_e += y;
		sum_dis_e += (LL)dis[x] * y;
		range_add(x, y);
		printf("%lld\n", getans(weight()));
	}
	return 0;
}