首页 > 代码库 > 旅行-树形DP

旅行-树形DP

技术分享

60分:对于每个点为根的情况做一遍DP,s,g表示从小C,A从这个点走出去的路程

100分,树形DP对于每个点的路径可以由其父亲转来,这样的DP就需要比较好的技巧了。

以前有道差不多的叫星座的题目来着。

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>using namespace std;#define ll long long int n,x,y,z,num;int head[300005],next[600005],to[600005],val[600005];ll f[300005],g[300005],fs[300005],gs[300005],ans[300005]; void add_edge(int u,int v,int c){    to[++num]=v;    val[num]=c;    next[num]=head[u];    head[u]=num; }void dp(int u,int fa){    bool son=0;    for(int edge=head[u];edge;edge=next[edge])    if(to[edge]!=fa)    {        son=1;        dp(to[edge],u);        f[u]=max(f[u],g[to[edge]]+val[edge]);        g[u]=min(g[u],f[to[edge]]+val[edge]);    }    if(!son) g[u]=0; }void DP(int u,int fa){    ll s1=1e16,s2=1e16;    int p1=0,p2=0;    for(int edge=head[u];edge;edge=next[edge])    if(to[edge]!=fa)    {        if(f[to[edge]]+val[edge]<s1)        {            s2=s1;            s1=f[to[edge]]+val[edge];            p2=p1;            p1=to[edge];        }else        if(f[to[edge]]+val[edge]<s2)        {            s2=f[to[edge]]+val[edge];            p2=to[edge];        }    }    for(int edge=head[u];edge;edge=next[edge])    if(to[edge]!=fa)    {        if(p1!=to[edge])        fs[to[edge]]=min(fs[to[edge]],s1+val[edge]);else        fs[to[edge]]=min(fs[to[edge]],s2+val[edge]);        fs[to[edge]]=min(fs[to[edge]],gs[u]+val[edge]);    }    ll g1=0,g2=0;    p1=0,p2=0;    for(int edge=head[u];edge;edge=next[edge])    if(to[edge]!=fa)    {        if(g[to[edge]]+val[edge]>g1)        {            g2=g1;            g1=g[to[edge]]+val[edge];            p2=p1;            p1=to[edge];        }else        if(g[to[edge]]+val[edge]>g2)        {            g2=g[to[edge]]+val[edge];            p2=to[edge];        }    }    for(int edge=head[u];edge;edge=next[edge])    if(to[edge]!=fa)    {        if(p1!=to[edge])        gs[to[edge]]=max(gs[to[edge]],g1+val[edge]);else        gs[to[edge]]=max(gs[to[edge]],g2+val[edge]);        gs[to[edge]]=max(gs[to[edge]],fs[u]+val[edge]);    }    for(int edge=head[u];edge;edge=next[edge])    if(to[edge]!=fa)    {        ans[to[edge]]=max(fs[to[edge]],f[to[edge]]);        DP(to[edge],u);    } } int main(){     scanf("%d",&n);     for(int i=1;i<=n-1;i++)     {         int u,v,c;         scanf("%d %d %d",&u,&v,&c);         add_edge(u,v,c);         add_edge(v,u,c);    }    memset(g,127,sizeof(g));    dp(1,0);    memset(fs,127,sizeof(fs));    ans[1]=f[1];gs[1]=1e6;fs[1]=0;    DP(1,0);    for(int i=1;i<=n;i++)    cout<<ans[i]<<endl;}

 

旅行-树形DP