人品问题树形dp

网上出现了一种高科技产品——人品测试器。只要你把你的真实姓名输入进去，系统将自动输出你的人品指数。把儿不相信自己的人品为0。经过了许多研究后，把儿得出了一个更为科学的人品计算方法。这种方法的理论依据是一个非常重要的结论：人品具有遗传性。因此，一个人的人品完全由他的祖先决定。把儿提出的人品计算方法相当简单，只需要将测试对象的k个祖先的人品指数（可能为负数）加起来即可。选择哪K个祖先可以由测试者自己决定，但必须要满足这个要求：如果除自己的父母之外的某个祖先被选了，那么他的下一代必需要选（不允许跳过某一代选择更远的祖先，否则将失去遗传的意义）。

非常不幸的是，把儿测试了若干次，他的人品值仍然不能为一个正数。现在把儿需要你帮助他找到选择祖先的最优方案，使得他的人品值最大。

输入格式：

数据的第一行是两个用空格隔开的正整数n和k，其中n代表把儿已知的家谱中共有多少人（包括把儿本身在内），k的意义参见问题描述。
数据的第二行有n-1个用空格隔开的整数（可能为负），这些数的绝对值在2^15以内。其中，第i个数表示编号为i+1的人的人品值。我们规定，编号为1的人是把儿。
接下来n行每行有两个用空格隔开的数，其中第i行的两个数分别表示第i个人的父亲和母亲的编号。如果某个人的父亲或母亲不在这个家谱内，则在表示他的父亲或母亲的编号时用0代替。
输入数据中除把儿以外的所有人都是把儿的祖先，他们都会在输入数据中作为父亲或母亲被描述到。输入数据中每个人都不可能同时作为多个人的父亲或者是母亲。

输出格式：

将把儿能够得到的最大人品值输出

样例输入：

6 3
-2 3 -2 3 -1
2 3
4 5
0 6
0 0
0 0
0 0

样例输出：

数据范围：

对于50%的数据，n<=10；
对于100%的数据，n<=100。

时间限制：

1000

空间限制：

10240

做法：

ans[i][j]表示编号为i的人选j个祖先及自身的最大人品值
ans[i][j]=a[i]+max{ans[lc[i]][k]+ans[rc[i]][j-k-1]}
(0<=k<=j-1,num[lc[i]]>=k,num[rc[i]]>=j-k-1 --> k>=j-num[rc[i]]-1)
直接设定ans[0][0]=0即可，不用加特判

 1 #include<cstdio>
 2 #include<cstring>
 3 typedef long long LL;
 4 bool vis[101];
 5 LL n,k;
 6 LL lc[101],rc[101],a[101];
 7 LL dp[101][101];
 8 LL num[101];//记录某结点及所有后代结点的总数量
 9 LL min(LL x,LL y)
10 {
11     return x>y?y:x;
12 }
13 LL max(LL x,LL y)
14 {
15     return x>y?x:y;
16 }
17 LL dfs(LL x)
18 {
19     num[x]=1;
20     if(lc[x])    num[x]+=dfs(lc[x]);
21     if(rc[x])    num[x]+=dfs(rc[x]);
22     return num[x];//改成这样提速效果不大
23 }
24 /*
25 LL dfs(LL x)
26 {
27     if(x==0)    return 0;
28     num[x]=dfs(lc[x])+dfs(rc[x])+1;
29     return num[x];
30 }
31 LL dp(LL i,LL j)
32 {
33     if(j==0)    return 0;
34      if(j==1)    return a[i];
35     LL k,ans1=-0x3f3f3f3f;
36     for(k=max(j-num[rc[i]]-1,0);k<=min(num[lc[i]],j-1);k++)
37         ans1=max(ans1,dp(lc[i],k)+dp(rc[i],j-k-1));
38     return ans1+a[i];//这样写T两个点
39 }//下面的貌似是类似常数优化的，不知道为什么差距这么大
40 //理论上不用记忆化，毕竟这个树形结构没有重叠子问题，也许是减少了函数调用次数 
41 */
42 void Dp(LL x)//直接处理完一个结点选任意数量子结点的答案
43 //这样写全部0ms过
44 {
45     dp[x][1]=a[x];
46     dp[x][0]=0;
47     if(lc[x])    Dp(lc[x]);
48     if(rc[x])    Dp(rc[x]);
49     int i,j;
50     for(i=2;i<=num[x];i++)
51     {
52         for(j=max(i-num[rc[x]]-1,0);j<=min(num[lc[x]],i-1);j++)
53             dp[x][i]=max(dp[x][i],dp[lc[x]][j]+dp[rc[x]][i-j-1]);
54             //傻了，曾经写成dp[x][i]=max(dp[lc[x]][j],dp[rc[x]][i-j-1]);了
55         dp[x][i]+=a[x];//曾经忘记//曾经将a[x]写成a[i]
56     }
57 }
58 /*
59 void Dp(LL x)//直接处理完一个结点选任意数量子结点的答案
60 //这样写也是全部0ms过
61 {
62     //dp[x][1]=a[x];
63     dp[x][0]=0;
64     if(lc[x])    Dp(lc[x]);
65     if(rc[x])    Dp(rc[x]);
66     int i,j;
67     for(i=1;i<=num[x];i++)
68     {
69         for(j=max(i-num[rc[x]]-1,0);j<=min(num[lc[x]],i-1);j++)
70             dp[x][i]=max(dp[x][i],dp[lc[x]][j]+dp[rc[x]][i-j-1]);
71 72         dp[x][i]+=a[x];
73     }
74 }
75 */
76 int main()
77 {
78     LL i;
79     memset(dp,136,sizeof(dp));
80     scanf("%lld%lld",&n,&k);
81     for(i=2;i<=n;i++)
82         scanf("%lld",&a[i]);
83     for(i=1;i<=n;i++)
84         scanf("%lld%lld",&lc[i],&rc[i]);
85     dfs(1);
86     //dp[0][1]=0;//不需要，因为num[0]=0，与0有关的最多只涉及到dp[0][0]
87     dp[0][0]=0;
88     Dp(1);
89     printf("%lld",dp[1][k+1]);//算上自己共要选k+1人
90     return 0;
91 }