给出一个 N 个节点的有根树，点编号 1 ～ N ，编号为 i 的点有权值 v i 。请选出一个包含树根的，点数 不超过 K 的连通块，使得点权和最大。
输入的第一行有二个整数 N , K ( K ≤ N ≤ 3000) 。
接下来一行 N 个整数，第 i 个数描述编号为 i 的点的父亲编号，若该数为 0 ，则表示点 i 为树根。
接下来一行 N 个整数，第 i 个数描述编号为 i 的点的权值。
输出一行一个整数，描述最大的点权和。保证答案不会超过 231?1231?1。
#include<iostream> #include<stdio.h> #include<algorithm> #include<stdlib.h> #include<cstring> const int MAXN=3010; using namespace std; struct edge{ int first; int next; int to; }a[MAXN*5]; int n,m,num=0,roof; int dp[MAXN][MAXN]; int W[MAXN]; void cl(){ memset(dp,0,sizeof(dp)); } void addedge(int from,int to){ a[++num].to=to; a[num].next=a[from].first; a[from].first=num; } void dfs(int now,int fa,int w){ if(w==0) return; for(int i=a[now].first;i;i=a[i].next){ int to=a[i].to; if(to==fa) continue; for(int j=1;j<=w;j++) dp[to][j]=dp[now][j]; dfs(to,now,w-1); for(int j=1;j<=w;j++) dp[now][j]=max(dp[now][j],dp[to][j-1]+W[to]); } } int main(){ cl(); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ int x; scanf("%d",&x); if(x==0) roof=i; else addedge(i,x),addedge(x,i); } for(int i=1;i<=n;i++) scanf("%d",&W[i]); dfs(roof,0,m); printf("%d",dp[roof][m-1]+W[roof]); }
原文：http://www.cnblogs.com/renjianshige/p/7198299.html