P1131 [ZJOI2007] 时态同步

显然这是一棵树。调整越靠根节点的树枝调整的代价越少。先找到最深的叶子节点，再从最小的子树开始，把所有子节点调整到同一深度，再调整子树上面的树枝。

记 d[x] 是 x 到叶子节点的最长距离，对于每一个 x 的子节点，代价为它们的距离差。

查看代码

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 5e5 + 10, M = 1e6 + 10;
int n, st;
LL ans, d[N];
int idx, hd[N], nxt[M], edg[M], wt[M];
void add(int a, int b, int c)
{
    nxt[++idx] = hd[a];
    hd[a] = idx;
    edg[idx] = b;
    wt[idx] = c;
}
void dfs(int x, int fa)
{
    for (int i = hd[x]; ~i; i = nxt[i])
        if (edg[i] != fa)
        {
            dfs(edg[i], x);
            d[x] = max(d[x], d[edg[i]] + wt[i]);
        }
    for (int i = hd[x]; ~i; i = nxt[i])
        if (edg[i] != fa)
            ans += d[x] - (d[edg[i]] + wt[i]);
}
int main()
{
    scanf("%d%d", &n, &st);
    for (int i = 1; i <= n; i++)
        hd[i] = -1;
    for (int i = 1, a, b, c; i < n; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }
    dfs(st, 0);
    printf("%d", ans);
    return 0;
}