问P2015（潍圭字山）

#include<bits/stdc++.h>
using namespace std;
int n,q,x,y,z,tmp,lson,rson,ll,rl;
int head[104],e[203],w[203],nxt[203],idx;
void add(int u,int v,int s){
	e[idx]=v;
	w[idx]=s;
	nxt[idx]=head[u];
	head[u]=idx;
	idx++;
	return;
}
vector<pair<int,int> >son[104];
int father[104];
int snum[104];
int dgr[104];
int cstdgr[104];
int dp[114][514];//在根为i的子树保留j个树枝
queue<int>qu;
bool vis[104];
void bfs(int bg){
	vis[bg]=1;
	qu.push(bg);
	while(qu.size()){
		tmp=qu.front();
		qu.pop();
		for(int i=head[tmp];i!=-1;i=nxt[i]){
			if(vis[e[i]])continue;
			qu.push(e[i]);
			vis[e[i]]=1;
			son[tmp].push_back({e[i],w[i]});
			father[e[i]]=tmp;
			dgr[tmp]++;
			cstdgr[tmp]++;
		}
	}
	return;
}
int main(){
	memset(dp,-1,sizeof(dp));
	memset(head,-1,sizeof(head));
	scanf("%d %d",&n,&q);
	for(int i=1;i<n;i++){
		scanf("%d %d %d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	bfs(1);//宽搜，给每条边定向
	for(int i=1;i<=n;i++)if(dgr[i]==0)qu.push(i);
	while(qu.size()){
		tmp=qu.front();//拓扑排序，同时dp
		qu.pop();
		snum[tmp]=1;
		for(auto i:son[tmp])snum[tmp]+=snum[i.first];
		dgr[father[tmp]]--;
		if(dgr[father[tmp]]==0)qu.push(father[tmp]);
		dp[tmp][0]=0;
		if(cstdgr[tmp]==0)continue;
		lson=son[tmp][0].first;
		rson=son[tmp][1].first;
		ll=son[tmp][0].second;
		rl=son[tmp][1].second;
		for(int i=1;i<snum[tmp];i++){
			dp[tmp][i]=max(dp[tmp][i],dp[lson][i-1]+ll);
			dp[tmp][i]=max(dp[tmp][i],dp[rson][i-1]+rl);
			if(i==1)continue;
			for(int ii=0;ii<snum[lson];ii++)dp[tmp][i]=max(dp[tmp][i],dp[lson][ii]+dp[rson][i-ii-2]+ll+rl);
		}
	}
	printf("%d",dp[1][q]);
	return 0;
}