POJ 2486 Apple Tree (树形dp 经典题)-蒲公英云

POJ 2486 Apple Tree (树形dp 经典题)

我就是我 2021-09-30 10:24 387阅读 0赞

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=105;
int head[maxn<<1],to[maxn<<1],val[maxn],nex[maxn<<1];
int F[maxn][maxn<<1],G[maxn][maxn<<1];
int cnt,V;
void addedge(int u,int v){
    nex[++cnt]=head[u],head[u]=cnt,to[cnt]=v;
}
void init(){
    memset(F,0,sizeof(F));
    memset(G,0,sizeof(G));
    memset(head,0,sizeof(head));
    memset(nex,0,sizeof(nex));
    cnt=0;
}
void dfs(int u,int fa){
    //for(int i=0;i<=V;++i)F[u][i]=G[u][i]=val[u];
    G[u][0]=F[u][0]=val[u];
    for(int v=head[u];v;v=nex[v])if(to[v]!=fa){
            dfs(to[v],u);
            for(int j=V;j>=0;--j)
                for(int k=0;k<=j;++k){
                    if(k>=2)G[u][j]=max(G[u][j],G[u][j-k]+G[to[v]][k-2]);
                    if(k>=2)F[u][j]=max(F[u][j],F[u][j-k]+G[to[v]][k-2]);
                    F[u][j]=max(F[u][j],G[u][j-k]+F[to[v]][k-1]);
                }
        }
}
int main(){
    int n;
    while(scanf("%d%d",&n,&V)!=EOF){
        init();
        for(int i=1;i<=n;++i)scanf("%d",&val[i]);
        for(int i=1;i<n;++i){
            int a,b;
            scanf("%d%d",&a,&b);
            addedge(a,b);
            addedge(b,a);
        }
        dfs(1,-1);
        int ans=0;
        for(int i=0;i<=V;++i)ans=max(ans,F[1][i]);
        printf("%d\n",ans);
    }
    return 0;
}