AFO

题解 P7232 【[JSOI2014] 支线剧情 2】

2021-01-13 22:20:49


考虑树形 DP。设 $f_u$ 为 $u$ 处有一个存档点,接下来不存档,访问完以 $u$ 为根的子树中所有剧情的最短时间。不难得到转移(这里的 $s_u$ 表示以 $u$ 为根的子树中叶子节点的个数)

$$f_u=\sum_{(u,v,w)\in E}f_v+s_v\times w$$

再设 $dp_u$ 为 $u$ 处有一个存档点,接下来可以存档,访问完以 $u$ 为根的子树中所有剧情的最短时间。考虑转移

  • 首先每个子节点 $v$ 可以不存档,最短时间为 $f_v+s_v\times w$,也可以存档,最短时间为 $dp_v+w+dep$($dep$ 为 $u$ 到根的距离)。
  • 然后因为 $u$ 有一个存档点,所以可以有至多一个子节点的最短时间变为 $dp_v+w$,枚举一下即可。

最后答案即为 $dp_1$。

代码还是去年写的。

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000000+10;

int n;

struct edge { int v,w,nxt; } e[N];
int head[N];
inline void addEdge(int u,int v,int w) {
    static int c=0;
    e[++c]=(edge){v,w,head[u]},head[u]=c;
}

ll s[N],f[N],dp[N];

inline void dfs(int u,ll d) {
    if (!head[u]) { s[u]=1; return; }
    ll tmp=0;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w;
        dfs(v,d+w); s[u]+=s[v],f[u]+=f[v]+1ll*s[v]*w;
        tmp+=min(f[v]+1ll*s[v]*w,dp[v]+d+w);
    }
    dp[u]=f[u];
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w;
        dp[u]=min(dp[u],tmp-min(f[v]+1ll*s[v]*w,dp[v]+d+w)+dp[v]+w);
    }
}

int main() {
    n=read();
    for (re int u=1;u<=n;++u) {
        for (re int k=read();k;--k) {
            int v=read(),w=read(); addEdge(u,v,w);
        }
    }
    dfs(1,0); printf("%lld\n",dp[1]);
    return 0;
}