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

我就是我 2021-09-30 10:24 260阅读 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;
    }

转载于:https://www.cnblogs.com/guangheli/p/9845207.html

发表评论取消回复

表情：

评论列表（有 0 条评论，260人围观）

还没有评论，来说两句吧...

相关阅读

相关树形dp HDU6867 Tree

[题目链接][Link 1] 多校，怎么越来越难了，是我变菜了吗。不多说，这是一道树形dp的题目，AC代码如下。 AC代码 include <cstdio

男娘i/ 2022年11月29日 03:03/ 0 赞/ 131 阅读

相关【POJ3321】Apple Tree

Apple Tree <table> <tbody> <tr> <td><strong>Time Limit:</strong> 2000MS</

今天药忘吃喽~/ 2022年09月25日 09:20/ 0 赞/ 143 阅读

相关树形dp入门之poj 2342

题目：[poj2342Anniversary party][poj2342_Anniversary party] 题意：话说一个公司的一些然要去参加一个party，

向右看齐/ 2022年08月23日 11:53/ 0 赞/ 150 阅读

相关 poj2342 树形dp入门

题意：公司要举办一次晚会，但是为了使得晚会的气氛更加活跃，每个参加晚会的人都不希望在晚会中见到他的直接上司，现在已知每个人的活跃指数和上司关系，求邀请哪些人来能使得晚会的总

心已赠人/ 2022年08月20日 16:06/ 0 赞/ 261 阅读

相关 poj1947Rebuilding Roads（树形dp）

题目：[poj1949Rebuilding Roads][] 题意：给出一棵树，问现在要得到一颗有p个节点的子树，需要最少减掉几条边？分析：首先可以明确是一个树形

妖狐艹你老母/ 2022年08月08日 03:28/ 0 赞/ 196 阅读

相关 POJ 3321-Apple Tree（树状数组）

Apple Tree <table> <tbody> <tr> <td><strong>Time Limit:</strong> 2000MS</td>

心已赠人/ 2022年07月26日 08:46/ 0 赞/ 179 阅读

相关 ural 1018-Binary Apple Tree【树状DP】

1018. Binary Apple Tree Time limit: 1.0 second Memory limit: 64 MB Let's imagine h

ゞ浴缸里的玫瑰/ 2022年07月24日 09:06/ 0 赞/ 165 阅读

相关 Apple Catching POJ - 2385 (DP)

It is a little known fact that cows love apples. Farmer John has two apple trees (which

小鱼儿/ 2022年02月25日 11:26/ 0 赞/ 191 阅读

相关 POJ-2486 Apple Tree 树形DP

题意：一棵n个点的树，每个点有苹果数vi，每条边长度为1。从树根1出发，你不能走多于m步，走到一个点就能获得该点苹果，问能获得最多苹果是多少个？解法：这道题想了挺久的还是没

朴灿烈づ我的快乐病毒、/ 2021年12月05日 04:41/ 0 赞/ 256 阅读

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

include<cstdio> include<cstring> include<algorithm> using namespace std;

我就是我/ 2021年09月30日 10:24/ 0 赞/ 261 阅读