首页 > itarticle > 「zjoi2009」时态同步 Solution Code

「zjoi2009」时态同步 Solution Code

admin 11月 13, 2020 0

一棵有$N$个结点，带边权的有根树，求至少需要增加多少边权才能使根结点到叶子结点的所有路径的权值和相同。

对于$100%$的数据，$N leq 500000$，边权$t_e leq 1000000$。

题目连接戳这里

Solution

树形$DP$的板子题。

令$dp_x$为叶子结点到$x$结点的最大时间。

则有 $dp_x = max (dp_{son[x]} + dis_{x, son[x]})$

因此 $ans = sum (dp_x - dp_{son[x]} - dis_{x, son[x]})$

Code


#include <cstdlib>
#include <iostream>
using namespace std;
#define MAXN 500500
#define int long long
int n, root, dp[MAXN], ans, fa[MAXN];
bool vis[MAXN];
struct  {
    int v, w;
    edge *next;
} pool[MAXN << 1], *h[MAXN], *cnt = pool;
inline void addedge(int u, int v, int w) {
    edge *p = ++cnt, *q = ++cnt;
    p->v = v, p->w = w, p->next = h[u], h[u] = p;
    q->v = u, q->w = w, q->next = h[v], h[v] = q;
}
inline void dfs(int u) {
    int v; vis[u] = true;
    for(edge *p = h[u]; p; p = p->next)
        if(!vis[v = p->v]) {
            fa[v] = u, dfs(v);
            dp[u] = max(dp[u], dp[v] + p->w);
        }
    for(edge *p = h[u]; p; p = p->next)
        if((v = p->v) != fa[u])
            ans += (dp[u] - dp[v] - p->w);
}
signed main() {
    int u, v, w;
    scanf("%lld%lld", &n, &root);
    for(int i = 1; i < n; i++) {
        scanf("%lld%lld%lld", &u, &v, &w);
        addedge(u, v, w);
    } dfs(root);
    printf("%lldn", ans);
    return 0;
}