参考链接：传送门
题解：
我们读完题目之后发现题目求最优解，那么这个最优解肯定要在众多可能中找最优的。我们从题目上发现某些密室在进去之前必须已经进入了其他密室。所以这里我们就可以用dfs来限制这一点。
首先先建树，之后就先求这个树的叶节点的各个最优解，然后再一步一步靠近树的根的节点。因为根节点的最优解肯定取决于叶节点
to：x的子节点
x：节点
y：可以去多少个密室
k：就是枚举从1—y
dp[x][y]：y个密室中肯定包含x，还要再找y-1个密室
dp[x][y]=max(dp[x][y],dp[x][k]+dp[to][y-k])
我们建树之后有可能建的树不止一颗，这样我们找一个公共节点，让从1--n的所有节点都是它的子节点，这样只需要找出来这个公共节点最优解就可以了
具体看代码：
1 #include<stdio.h> 2 #include<string.h> 3 #include<vector> 4 #include<iostream> 5 using namespace std; 6 const int maxn=250; 7 vector<int>w[maxn]; 8 int dp[maxn][maxn],vis[maxn]; 9 int n,m; 10 11 void dfs(int now){ 12 vis[now]=1; 13 int len=w[now].size(); 14 for(int i=0;i<len;++i){ 15 int to=w[now][i]; 16 if(vis[to]==0) dfs(to); 17 for(int j=m;j>=2;j--){ //这个m为什么是倒着循环的，原因为正着的话可能会导致某个密室进入了两次，同时它的宝藏也加了两次 18 for(int k=1;k<j;++k){ //倒着循环的话这个k<j就不会出现着一种情况 19 if(dp[to][j-k]!=-1 && dp[now][k]!=-1){ 20 dp[now][j]=max(dp[now][j],dp[now][k]+dp[to][j-k]); //为什么可以写成+的形式 21 } //因为dp[now][j]就表明now这个密室已经进入过了，这样的话，就可以进入now的子密室 22 } 23 } 24 } 25 } 26 27 int main(){ 28 while(~scanf("%d%d",&n,&m) && (n+m)) 29 { 30 memset(vis,0,sizeof(vis)); 31 memset(dp,-1,sizeof(dp)); 32 for(int i=0;i<=n;++i) 33 w[i].clear(),dp[i][0]=0; 34 dp[0][1]=0; 35 for(int i=1;i<=n;++i){ 36 int a,b; 37 scanf("%d%d",&a,&b); 38 w[a].push_back(i); 39 dp[i][1]=b; 40 } 41 m++; 42 dfs(0); 43 printf("%d\n",dp[0][m]); 44 } 45 return 0; 46 }
原文：https://www.cnblogs.com/kongbursi-2292702937/p/11620848.html
