T2 [ZJOI2007] 时态同步

传送门：luogu P1131

题目要求我们用最少的代价使根节点到每个叶子节点的距离相等
那如何使代价最小呢，对于下面这种情况

对于有同一个父亲节点的两个叶子节点，一个的代价为5，一个代价为3，他们都加了一个
代价3，这样我们可以把3加到父亲节点到根节点的树枝上，这样可以省去重复加的代价，
也就是说，调整越靠近根节点的树枝我们的代价就越少，那么我们从下向上更新，使每一
个子树中的节点的深度相同，每次调整的代价就是ans += (dis[u] - (dis[v] + e[i].w));
\(dis[u]\) 是指 \(u\) 到叶子节点的最大深度；

代码：

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

const int maxn = 5e5 + 5;
int n, tot, head[maxn], cd[maxn];
ll maxx;
struct edge {
	int v, nxt;
	ll w;
} e[maxn];

void add(int u, int v, int w) {
	e[++ tot] = {v, head[u], (ll)w};
	head[u] = tot;
}

ll dis[maxn], ans;
void dfs(int u, int fa) {
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if (v == fa) continue ;
		dfs(v, u);
		dis[u] = max(dis[u], dis[v] + e[i].w);
	}
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if (v == fa) continue ;
		ans += (dis[u] - (dis[v] + e[i].w));
	}
}

void read() {
	int s;
	scanf("%d%d", &n, &s);
	for (int i = 1, u, v, w; i < n; ++ i) {
		scanf("%d%d%d", &u, &v, &w);
		add(u, v, w), add(v, u, w);
	}
	dfs(s, 0);
	printf("%lld\n", ans);
}

int main() {
	read();
	return 0;
}