题目：P2015 二叉苹果树

测评记录：38pts

#include<bits/stdc++.h>
using namespace std;
const int N=101;

int n,q;
vector<pair<int,int> >tr[N];
int f[N][N];

void dfs(int x,int fa)
{
	//cout<<x<<' '<<fa<<endl;
	int y[2],w[2],cnt=0;
	for(int i=0;i<tr[x].size();i++)
	{
		y[cnt]=tr[x][i].first; w[cnt]=tr[x][i].second;
		if(y[cnt]==fa) continue ;
		dfs(y[cnt],x);
		cnt++;
	}
	if(cnt==0) return ;
	for(int k=q;k>0;k--)
	{
		f[x][k]=max(f[x][k],f[y[0]][k-1]+w[0]);
		f[x][k]=max(f[x][k],f[y[1]][k-1]+w[1]);
		for(int i=1;i<k;i++)
		{
			int j=k-i;
			f[x][k]=max(f[x][k],f[y[0]][i-1]+w[0]+f[y[1]][j-1]+w[1]);
		}
	}
}
int main()
{
	cin>>n>>q;
	for(int i=1;i<n;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		tr[u].push_back(make_pair(v,w));
		tr[v].push_back(make_pair(u,w));
	}	
	
	dfs(1,0);
	//cout<<tr[3].size();
	cout<<f[1][q];
	/*
	cout<<"\n------------\n";
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=q;j++)
		{
			cout<<f[i][j]<<' ';
		}cout<<endl;
	}
	*/
}

样例：

99 12 1 39 0 1 79 0 2 58 1 2 89 0 4 7 0 4 32 0 5 9 0 5 75 0 6 42 0 6 52 0 10 29 0 10 67 0 12 16 0 12 77 23 13 18 0 13 46 67 15 85 0 15 98 0 17 26 0 17 66 0 19 33 0 19 49 0 22 70 0 22 84 0 23 50 0 23 99 0 25 51 0 25 92 0 33 34 0 33 47 0 34 37 45 34 62 0 35 44 8 35 94 7 36 27 0 36 59 0 38 36 6 38 64 0 39 23 0 39 43 0 41 5 0 41 12 0 42 3 0 42 60 0 43 19 0 43 93 0 44 24 0 44 80 0 45 96 0 45 97 0 47 53 0 47 55 3 48 8 0 48 31 0 49 2 0 49 81 0 50 35 0 50 82 0 52 14 0 52 95 0 61 41 0 61 45 0 63 57 0 63 69 0 64 78 0 64 86 0 70 28 0 70 30 0 72 4 0 72 13 0 74 88 0 74 91 0 79 61 0 79 74 0 81 65 0 81 68 0 82 17 0 82 63 0 84 71 0 84 76 0 87 10 0 87 15 0 88 25 0 88 90 0 90 21 0 90 40 0 91 6 0 91 48 0 93 22 2 93 87 0 94 73 0 94 83 0 96 20 0 96 56 0 97 11 0 97 54 0 99 38 0 99 72 0

答案

112

感觉很诡异求调