我们常常用链式前向星来写树形dp问题。但是我认为vector数组加上对于子树个数的优化常常会更加简洁好写。（邻接表和邻接矩阵也是可以使用的，但是我感觉vector真的太简单了

P1122是一个无根树形dp的问题，所以要把每一个节点视为根进行遍历。 P1273和P2074本质上是一个题目，都是采用对当前成本的规划。而这三个题目都可以用vector来实现。

具体实现方法如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=305;
const int inf=0x3ffff;

vector<int>E[maxn];//store the son
int dp[maxn][maxn];//dp[i][j]represents the value of i node including j son
int val[maxn];//value of each son( not the edge but can be seen as edge)

//opmitize of time by tracking the excect number of sons 
int dfs(int u,int m){
	dp[u][1]=val[u];
	int sizeu=1,sizev=0;//the son tree size with root u,v
	for(int i=0;i<E[u].size();i++){
		int v=E[u][i];
		sizev=dfs(v,m-1);
		for(int j=m;j>=1;j--)//分组背包 
			for(int k=1;k<=sizev&&k<j;k++)
				dp[u][j]=max(dp[u][j],dp[v][k]+dp[u][j-k]);
		sizeu+=sizev;
	}
	return sizeu;
}

//didn't optimized
//void dfs(int u,int m){
//	dp[u][1]=val[u];
//	for(int i=0;i<E[u].size();i++){
//		int v=E[u][i];
//		dfs(v,m-1);
//		for(int j=m;j>=1;j--){
//			for(int k=1;k<j;k++){
//				dp[u][j]=max(dp[u][j],dp[v][k]+dp[u][j-k]);
//			}
//		}
//	}
//}
int main(){
	int n,m;
	cin>>n>>m;
	m++;//add a super root
	for(int i=1;i<=n;i++){
		int a;	
		cin>>a>>val[i];
		E[a].push_back(i);
	}
	dfs(0,m);
	cout<<dp[0][m]<<endl;
}

好吧但是我不知道这个为什么不需要记忆化，记忆化优化就是加一个bool vis[maxn]的数组去判断是否访问过子节点如果访问过直接返回即可