BZOJ 3743 Kamp（树形DP）

题目链接：BZOJ 3743

题目大意：给出n个点n-1条边的一棵树，边有边权，有K个关键点，对于i=1~n，计算从第i个点起遍历K个关键点（不要求最后回到点i）经过的路径总长度的最小值。

题解：如果起点是K个关键点之一，答案会是2倍的K个关键点组成的虚树的边权和，再减去起点到剩下K-1个关键点的路径长度的最大值。如果起点不是K个关键点之一，答案会是起点到某个关键点的路经长度，加上以这个关键点为起点、遍历其余K-1个关键点的答案。
这个可以树形DP来求，详见代码及注释。

code(第一次写这种还要合并父节点信息的DP，感觉还是蛮巧妙的(*^▽^*))

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 500005
using namespace std;
typedef long long ll;
inline int read()
{
    char c=getchar(); int num=0,f=1;
    while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }
    while (c<='9'&&c>='0') { num=num*10+c-'0'; c=getchar(); }
    return num*f;
}
struct edge{
    int to,ne,val;
}e[N<<1];
int n,m,tot,head[N],num[N],tag[N],t[N];
ll f[2][N],dis[N],ans[N];
inline void push(int x,int y,int w)
{
    e[++tot].to=y; e[tot].val=w; e[tot].ne=head[x]; head[x]=tot;
    e[++tot].to=x; e[tot].val=w; e[tot].ne=head[y]; head[y]=tot;
}
void dp(int now,int pre)
{
    num[now]=tag[now];  //num[now]表示以now为根的子树内的关键点数
    for (int i=head[now];i;i=e[i].ne)
    {
        int v=e[i].to; if (v==pre) continue;
        dp(v,now); if (!num[v]) continue;
        num[now]+=num[v]; dis[now]+=dis[v]+e[i].val;
        //dis[now]表示节点now到子树内所有关键点的路径长度的并
        int tmp=f[0][v]+e[i].val;
        if (tmp>f[0][now]) f[1][now]=f[0][now],f[0][now]=tmp;
         else if (tmp>f[1][now]) f[1][now]=tmp;
        //f[0/1][now]记录节点now向下走到子树内关键点的最大、次大路径长（来自不同子树）
    }
}
void pushdown(int now,int pre)  //整个子树的最优转移已经确定了，直接更新答案
{
    for (int i=head[now];i;i=e[i].ne)
    {
        int v=e[i].to; if (v==pre) continue;
        ans[v]=ans[now]+e[i].val;
        pushdown(v,now);
    }
}
void dfs(int now,int pre,ll up,ll sum) //up表示节点now向上走走到一个关键点的最大路径长
{
    ans[now]=2*sum-max(up,f[0][now]);
    for (int i=head[now];i;i=e[i].ne)
    {
        int v=e[i].to; if (v==pre) continue;
        if (num[v])
        {
            ll tmp=0;
            if (up||tag[now]) tmp=max(tmp,up+e[i].val);
            if (f[0][now]==f[0][v]+e[i].val) 
            {
                if (f[1][now]) tmp=max(tmp,f[1][now]+e[i].val);
            }
            else tmp=max(tmp,f[0][now]+e[i].val);
            dfs(v,now,tmp,sum);
        }
        else
        {
            ans[v]=ans[now]+e[i].val;
            pushdown(v,now);
        }
    }
} 
int main()
{
    n=read(); m=read();
    for (int i=1;i<n;i++)
    {
        int x=read(),y=read(),w=read();
        push(x,y,w);
    }
    for (int i=1;i<=m;i++)
    {
        t[i]=read();
        tag[t[i]]=1;
    }
    dp(t[1],0);
    dfs(t[1],0,0,dis[t[1]]);
    for (int i=1;i<=n;i++) printf("%lld\n",ans[i]);
    return 0;
}