ダイヤを集める

ダイヤを集める
Description
 
ニンニクにはn都市があり、番号は1からnまでで、都市間にはn−1の道路があり、任意の2つの都市間が連通していることを保証している.都市ごとにダイヤモンドが一定数あります.
ニンニク君はニンニクの国でダイヤモンドを集めたい.彼は都市1を出発して、毎日都市間の道路を通って別の都市まで車を運転することができます.ニンニクが初めて都市に着いたとき、彼はこの都市のすべてのダイヤモンドを集めることができて、もし彼が後ろにこの都市に来たら、レンガや石を集めることができませんでした.
ニンニク君はK日しかありません.ニンニク君がどれだけのダイヤモンドを集めることができるか計算してください.
Input
 
1行目は3つの整数n(1≦n≦100),K(0≦k≦200)を入力し,合計n都市,ニンニク君にK日間の時間があることを示した.
次の行に、各都市のダイヤモンドの数を表すn個のスペースで区切られた整数を入力します.都市ごとのダイヤモンドの数は1000以下です.
次にn−1行を入力し、各行に2つの整数a(1≦a≦n)、b(1≦b≦n)を入力し、都市aと都市bの間に双方向道路が存在することを示す.
Output
 
1行1個の整数を出力してニンニク君が最大で入手できるダイヤモンドの数を表します.
Sample Input 1

3 2
3 8 3
1 3
3 2

Sample Output 1

14

Sample Input 2

6 2
5 9 8 4 9 2
1 6
6 2
2 5
5 3
5 4

Sample Output 2

16

Source
ニンニクの客を計る
题意分析:n个のノードがあって、n-1本の辺、连通して、简単に1本の木だと思い付くことができて、また最大値を求めさせて、自然と木の形のDPを连想しました;元の問題は--あなたに1本の木をあげて、すべての辺(双方向)の権値は1で、すべてのノードは一定の価値があってしかも1回しか取ることができなくて(注意して必ず帰ってきてやっと同層の別の子の木に着くことができます)、k日を見て、取ることができる最大の価値を聞きます;
テーマ分析:サブツリーごとに、その子の木は1つ以上(時間が十分な場合)に行くことができて、しかも1本の木ごとに2つの操作があります--行って帰ってきたのと行ったのではありません;行って帰ってきたのは比較的によく考えます--もし根のノードが行って帰ってくるならば、そのすべての子の木は行ってすべて帰って、とても簡単に1つの木の上のパケットのリュックサックを叩くことができます(具体的な操作は言うまでもなく);しかし面倒なのは帰らない情況--多くの帰ってくる字の木があることができて、しかし1つの帰ってこない子の木しかなくて、慣性の思惟によって、多重のリュックサックが帰ってくる情況を考え出した後に、1つの帰ってこない子の木を確定することを考えて、更に残りの子の木の中で1回のグループのリュックサックをして、最大の値を取って、私はこのようなごみを収めて考えます次元の影响は长い间苦労して(泣きたくて涙がありません)、次はまず私の70点のコードを送ります(実は详しく処理して満点になるべきです):

#include
using namespace std;
int n,m,ma[1100],dp[1100][2100][2];
vector vec[1100];
void dfs(int a,int b,int c,int fa)
{//cout<=2;j-=2)
{
for(int e=0;e<=j;e+=2)
{
dp2[j]=max(dp2[j],dp2[j-e]+dp[vec[a][i]][e][1]);
dp2[j+1]=dp2[j];
//cout<=2;j-=2)
{
for(int e=0;e<=j;e+=2)
{
dp2[j]=max(dp2[j],dp2[j-e]+dp[vec[a][i]][e][1]);
dp2[j+1]=dp2[j];
}
}
}
for(int i=1;i<=b;i++)
{
for(int j=1;j<=i-1;j++)	
{//cout<>n>>m;
for(int i=1;i<=n;i++)
{
cin>>ma[i];
}
for(int i=1;i>a>>b;
vec[a].push_back(b);
vec[b].push_back(a);
}
dfs(1,m,1,-2);
dfs(1,m,0,-2);
cout<

ちょっと长いです.
次に正解の考え方(簡潔):まず初値dp[u][a][b]をuノードの値に割り当てるのは当然であり、それから子ノードを列挙し(親ノードに列挙しないように注意)、次の層のdp[v][a][b](それがなければ大きな問題は解決できず、体の過程は深く考えない)、さらに0->mを列挙する(mは最大日数)は、前に打ち出された量の日数e(0->j-1)に列挙され、前に打ち出されたものと現在のものが1つしか戻ってこないので、方程式をリストするのは難しくない:戻る場合:dp[u][j][1]=max(dp[u][j][1],dp[u][e][1]+dp[v][j-e-2][1]);戻らない場合:dp[u][j][0]=max(dp[u][j][0],dp[u][e][0]+dp[v][j-e-2][1]);dp[u][j][0]=max(dp[u][j][0],dp[u][e][1]+dp[v][j-e-1][0]);
ACコード:

#include
using namespace std;
int n,m,dp[210][210][2],ma[210];
vector vec[210];
void dfs(int fa,int u)
{
	int l=vec[u].size();
	for(int i=0;i<=m;i++)
	{
		dp[u][i][1]=dp[u][i][0]=ma[u];
	}
	for(int i=0;i=1;j--)
		{
			for(int e=0;e<=j-1;e++)
			{
				if(j-e>=2)
				{
					dp[u][j][1]=max(dp[u][j][1],dp[u][e][1]+dp[v][j-e-2][1]);
					dp[u][j][0]=max(dp[u][j][0],dp[u][e][0]+dp[v][j-e-2][1]);//      
				}
				dp[u][j][0]=max(dp[u][j][0],dp[u][e][1]+dp[v][j-e-1][0]);//      
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>ma[i];
	}
	for(int i=1;i>a>>b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	dfs(-1,1);
	cout<