• 欢迎光临~

[ZJOI12007] 时态同步

开发技术 开发技术 2022-07-28 次浏览

[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_{sonin x}{F(son)}+sum_{sonin 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("%lldn", f[s]);
    return 0;
}
程序员灯塔
转载请注明原文链接:[ZJOI12007] 时态同步
喜欢 (0)