BZOJ3743 COCI2015Kamp（树形dp）

　　设f[i]为由i开始遍历完子树内所要求的点的最短时间，g[i]为由i开始遍历完子树内所要求的点最后回到i的最短时间。则g[i]=Σ(g[j]+2)，f[i]=min{g[i]-g[j]+f[j]-1}。

　　然后由父亲答案还原。因为上面的dp用到了max似乎不太好搞，于是记录一下最大值是用了哪棵子树以及次大值就行了。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 500010

#define ll long long

int n,m,a[N],id[N],p[N],size[N],t=;

ll f[N],f2[N],g[N];

bool flag[N];

struct data{int to,nxt,len;

}edge[N<<];

void addedge(int x,int y,int z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;}

inline ll noback(int x,int y,int z){return g[x]-g[y]+f[y]-z;}

void dfs(int k,int from)

{

    size[k]=flag[k];

    for (int i=p[k];i;i=edge[i].nxt)

    if (edge[i].to!=from)

    {

        dfs(edge[i].to,k);

        size[k]+=size[edge[i].to];

        if (size[edge[i].to]) g[k]+=g[edge[i].to]+(edge[i].len<<);

    }

    f[k]=f2[k]=g[k];

    for (int i=p[k];i;i=edge[i].nxt)

    if (edge[i].to!=from&&size[edge[i].to])

    {

        ll x=noback(k,edge[i].to,edge[i].len);

        if (x<f[k]) f2[k]=f[k],f[k]=x,id[k]=edge[i].to;

        else if (x<f2[k]) f2[k]=x;

    }

}

void getans(int k,int from)

{

    for (int i=p[k];i;i=edge[i].nxt)

    if (edge[i].to!=from)

    {

        if (size[edge[i].to])

        {

            if (size[edge[i].to]<m)

            {

                ll x=f[k],y=g[k];

                g[k]-=g[edge[i].to]+(edge[i].len<<);

                if (id[k]==edge[i].to) f[k]=f2[k]-(g[edge[i].to]+(edge[i].len<<));

                else f[k]=f[k]-(g[edge[i].to]+(edge[i].len<<));

                g[edge[i].to]=y;

                if (noback(edge[i].to,k,edge[i].len)<f[edge[i].to]+g[k]+(edge[i].len<<))

                f2[edge[i].to]=f[edge[i].to]+g[k]+(edge[i].len<<),id[edge[i].to]=k,f[edge[i].to]=noback(edge[i].to,k,edge[i].len);

                else f[edge[i].to]+=g[k]+(edge[i].len<<),f2[edge[i].to]=min(f2[edge[i].to]+g[k]+(edge[i].len<<),noback(edge[i].to,k,edge[i].len));

                f[k]=x,g[k]=y;

            }

        }

        else g[edge[i].to]=g[k]+(edge[i].len<<),f[edge[i].to]=f[k]+edge[i].len;

        getans(edge[i].to,k);

    }

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj3743.in","r",stdin);

    freopen("bzoj3743.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read();

    for (int i=;i<n;i++)

    {

        int x=read(),y=read(),z=read();

        addedge(x,y,z),addedge(y,x,z);

    }

    for (int i=;i<=m;i++) flag[read()]=;

    dfs(,);

    getans(,);

    for (int i=;i<=n;i++) printf(LL,f[i]);

    return ;

}

巴特西

BZOJ3743 COCI2015Kamp（树形dp）

最新文章

热门文章