感觉codeforces也是来到了能做D题的水平。
在解决完子区间的查询问题之后，感觉C题能做的就多了。

codeforces的D题多是一些C题的加强版，这里往往涉及到某些规律，例如二进制位。

同样D题往往也容易出现一些简单的树和图的问题，尽管我目前的水平仍然做不出来，但是可以知道的是D题并不是太不可做的树图题。

在两天的专研中也是找到了一个适合自己的树图做题法，就是邻接表。

用邻接表进行存图，需要剪枝用tsize数组来看枝叶的大小，剩下的就是遍历+dfs+dp。

不需要存图的时候，直接遍历+dfs+dp。

对于树形dp的dp问题，单拎出来感觉并不是很难写的dp。主要的问题可能还是在于分析树形dp。

1.上司的舞会。不需要剪去枝叶。而是在邻近节点中进行选择，因此不需要进行tsize记录枝叶大小。f[n][2]也是我比较擅长的dp方式，用于使用或否。

对于dp的递推也并不是很难，主要在于邻近节点的比较问题。

2.二叉苹果树。需要剪去枝叶。因此我们可以采用tsize数组来表示枝叶大小。通过有依赖的背包问题分析，配合tsize进行剪枝，从而得到我们所想要留下的苹果数。

3.选课问题，类似苹果数，不需要双向建图，需要对0处进行修改。

4.加分二叉树。不需要剪枝，选择保留与否，类似上司的舞会。只需要开线性dp，因为我们考虑的只是大小问题，不存在中间节点没有，其他节点存在的情况。只需要对正数子树进行相加即可。

无需剪枝叶code：

void dfs(int u){
	f[u][0] = 0;
	f[u][1] = happy[u];
	for(auto i:ve[u]){
		dfs(i);
		f[u][1] += f[i][0];
		f[u][0] += max(f[i][0],f[i][1]);
	}
}
int main()
{
 	//cin.ignore(numeric_limits<streamsize>::max(),'\n')
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>happy[i];
	}
	int a,b;
	for(int i=1;i<n;i++){
		cin>>a>>b;
		ve[b].push_back(a); 
		sign[a] = true;
	}
	int root = -1;
	for(int i=1;i<=n;i++)
		if(!sign[i]) {root=i;break;}
	dfs(root);
	cout<<max(f[root][0],f[root][1])<<endl;;
}

需要剪掉枝叶，存在依赖关系，有依赖的背包问题code：

void dfs(int u,int fa){
	tsize[u] = 1;//记录枝叶的大小。 
	for(auto i:ve[u]){
		int v = i.v,w = i.w;
		if(v==fa)
			continue;
		dfs(v,u);
		tsize[u]+=tsize[v];
		for(int j=min(tsize[u]-1,q);j;j--){//倒序递推可以参考有依赖的背包问题。用到之前子节点对应的值  j-k-1; 
			for(int k=min(tsize[v]-1,j-1);k>=0;k--){//遍历子节点的子树所以正序倒序都可以 
				f[u][j] = max(f[u][j],f[u][j-k-1]+f[v][k]+w); //状态转移方程可以参考有依赖的背包问题。 
			}
		}
	}
}
int main()
{
 	//cin.ignore(numeric_limits<streamsize>::max(),'\n')
	cin>>n>>q;
	int a,b,c;
	for(int i=1;i<n;i++){
		cin>>a>>b>>c;
		ve[a].push_back({b,c});
		ve[b].push_back({a,c});//双向存边 
	}
	dfs(1,1);
	cout<<f[1][q]<<endl;//f[i][j] 表示以i为节点保留q个枝叶时的最大值 
}