bzoj 3743 [Coci2015]Kamp——树形dp+换根

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3743

树形dp+换根。 “从根出发又回到根” 减去 “mx ” 。

注意dfsx里真的要改那些dp[cr]，为了下一层的调用。而且还要改回来！为了其他孩子下一层的调用！

注意dfsx里真的要改那些dp[v]，为了下一层的调用。而且还要改回来！为了本层的继续调用！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=5e5+5;
int n,m,hd[N],xnt,num[N];
ll mx[N],dp[N],ans[N];
bool b[N];
struct Ed{
    int nxt,to,w;
    Ed(int n=0,int t=0,int w=0):nxt(n),to(t),w(w) {}
}ed[N<<1];
void add(int x,int y,int z)
{
    ed[++xnt]=Ed(hd[x],y,z);hd[x]=xnt;
    ed[++xnt]=Ed(hd[y],x,z);hd[y]=xnt;
}
void updt(int cr,int v,int i)
{
    if(num[v])
    {
        num[cr]+=num[v];
        dp[cr]+=dp[v]+(ed[i].w<<1);
        mx[cr]=max(mx[cr],mx[v]+ed[i].w);
    }
}
void dfs(int cr,int f)
{
    if(b[cr])num[cr]=1;
    for(int i=hd[cr],v;i;i=ed[i].nxt)
        if((v=ed[i].to)!=f)
        {
            dfs(v,cr);
            updt(cr,v,i);
        }
}
void dfsx(int cr,int f)
{
    int ynm=num[cr];ll ymx=mx[cr],ydp=dp[cr];
    for(int i=hd[cr],v;i;i=ed[i].nxt)
        if((v=ed[i].to)!=f)
        {
            dp[cr]=ydp;mx[cr]=ymx;num[cr]=ynm;
            int tnm=num[v];ll tmx=mx[v],tdp=dp[v];
            
            if(num[v])
            {
                num[cr]-=num[v];
                dp[cr]-=dp[v]+(ed[i].w<<1);
            }
            mx[cr]=0;
            for(int j=hd[cr],u;j;j=ed[j].nxt)
                if((u=ed[j].to)!=v&&num[u])mx[cr]=max(mx[cr],mx[u]+ed[j].w);
            
            updt(v,cr,i);
            ans[v]=dp[v]-mx[v];
            dfsx(v,cr);
            num[v]=tnm;mx[v]=tmx;dp[v]=tdp;
        }
}
int main()
{
    scanf("%d%d",&n,&m);int x,y,z;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    for(int i=1;i<=m;i++)
        scanf("%d",&x),b[x]=1;
    dfs(1,0);
    ans[1]=dp[1]-mx[1];
    dfsx(1,0);
    for(int i=1;i<=n;i++)printf("%lld
",ans[i]);
    return 0;
}