[ZJOI12007] 时态同步

[ZJOI2007] 时态同步 – 洛谷

将图看成以激发器 /(S/) 为根的一棵树。

容易发现，所有终止节点均为叶子节点，于是题意转化为：至少改动多少次边权使得 “时态同步”。

设 /(u, v/) 为两个不同的叶子节点。

那么，若 /(u,v/) 时态同步，则在以 /(lca(u,v)/) 为根的子树中，从 /(lca(u,v)/) 到 /(u,v/) 的时态也同步。这是因为在 /(lca(u,v)/) 以上 /(u,v/) 到 /(S/) 的路径就重叠了。

如上，可知若在以 /(S/) 为根的树中时态同步，则在其任意一棵子树中，时态必定也同步。

考虑树形 /(DP/) ：

设 /(F(x)/) 表示使以 /(x/) 为根的子树时态同步所需的最小次数。

/(path(x)/) 表示时态同步时，从 /(x/) 到叶子节点的路径长度。

再设 /(MaxPath/) 表示未经操作时，/(x/) 到叶子节点的最长路径。

容易得出转移方程：

/[F(x)=/sum_{son/in x}{F(son)}+/sum_{son/in x}{MaxPath-path(son)-edge(x,son)}
/]

完美解决。

#include <bits/stdc++.h>
#define rep(var, st, ed) for(int var = st; var <= ed; var++)
#define fin freopen("in", "r", stdin)
#define fout freopen("out", "w", stdout)
namespace IO{
    template <typename T>
    inline void read(T &x)
    {
        x = 0;
        T w = 1;
        char ch = getchar();
        while (ch < '0' || ch > '9') { if (ch == '-') w = -1;ch = getchar();}
        while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
        x = x * w;
    }
    template <typename T, typename... Args>
    inline void read(T &x, Args&... args) {read(x);read(args...);}
};
using IO::read;
using LL = long long;
const int N = 500010;
int n, s;
LL f[N], path[N];
struct Node {
    int id;
    LL cost;
}; std::vector<Node> G[N];
void dp(int x, int fa)
{
    LL Max = 0;
    for (auto son : G[x])
    {
        if (son.id == fa) continue;
        dp(son.id, x);
        f[x] += f[son.id], Max = std::max(Max, path[son.id] + son.cost);
    }
    path[x] = Max;
    for (auto son : G[x])
        if (son.id != fa) f[x] += Max - path[son.id] - son.cost;
}
int main()
{
    read(n, s);
    rep(i, 1, n - 1)
    {
        int u, v; LL t;
        read(u, v, t);
        G[u].push_back((Node){v, t});
        G[v].push_back((Node){u, t});
    }
    dp(s, 0);
    printf("%lld/n", f[s]);
    return 0;
}