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;
}