「题解注释」P3345 [ZJOI2015] 幻想乡战略游戏

题解 P3345 【[ZJOI2015]幻想乡战略游戏】 - Baka's Blog - 洛谷博客 (luogu.org)

耗时：半个下午

代码注释：

#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) { // 修改到链顶的 dis 总和
	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) { // 查询到链顶的 dis 总和，可以参考 lca 的深度求法
	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) {
	// dis[x, root] * e[y] + dis[rt, root] * e[y] - 2 * range(x, root)
	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); // 求重儿子的 dfs
	dfs2(1, 1); // 重链剖分二阶段
	build(1, 1, n); // “摆树枝”
	
	while (m--) {
		int x = rd(), y = rd(); // 在 x 点上放 y 个军队
		sum_e += y; // 军队总和
		sum_dis_e += (LL)dis[x] * y; // 求总和
		range_add(x, y);
		printf("%lld\n", getans(weight()));
	}
	return 0;
}