P2015 二叉蘋果樹
時間限制 1.00s
內存限制 125.00MB
題目描述
有一棵蘋果樹，如果樹枝有分叉，一定是分2叉（就是說沒有只有1個兒子的結點）

這棵樹共有N個結點（葉子點或者樹枝分叉點），編號為1-N,樹根編號一定是1。

我們用一根樹枝兩端連接的結點的編號來描述一根樹枝的位置。下面是一顆有4個樹枝的樹

2 5
\ /
3 4
\ /
1
現在這顆樹枝條太多了，需要剪枝。但是一些樹枝上長有蘋果。

給定需要保留的樹枝數量，求出最多能留住多少蘋果。

輸入格式
第1行2個數，N和Q(1<=Q<= N,1<N<=100)。

N表示樹的結點數，Q表示要保留的樹枝數量。接下來N-1行描述樹枝的信息。

每行3個整數，前兩個是它連接的結點的編號。第3個數是這根樹枝上蘋果的數量。

每根樹枝上的蘋果不超過30000個。

輸出格式
一個數，最多能留住的蘋果的數量。

輸入輸出樣例
輸入 #1 復制
5 2
1 3 1
1 4 10
2 3 20
3 5 20
輸出 #1 復制
21

解題思路：
$dp[u][j]$：以第$u$節點為根的子樹保留$j$所留下的最大蘋果數
則：$dp[u][j]=max(dp[u][j],dp[u][j?k]+dp[v][k?1]+val)$
因此要先一個循環遍歷$j$的值，$j$最多的值為樹的邊數與需保留的邊數的較小值
還需遍歷$k$的值，即其子樹能保留的邊數

代碼：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queue<int,vector<int> ,greater<int> >q;
const int maxn = (int)1e5 + 5;
const ll mod = 1e9+7;
struct node
{int to;int val;node(int _to,int _val) {to=_to;val=_val;}
};
vector<node> m[120];
int n,k;
int dp[120][120];
int dfs(int s,int f) {int d=0;for(int i=0;i<m[s].size();i++) {if(m[s][i].to==f) continue;d+=dfs(m[s][i].to,s)+1;for(int j=min(k,d);j>0;j--) {for(int t=min(j,d);t>0;t--) {dp[s][j]=max(dp[s][j],dp[m[s][i].to][t-1]+dp[s][j-t]+m[s][i].val);}}}return d;
}
int main() 
{#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);#endif//freopen("out.txt", "w", stdout);//ios::sync_with_stdio(0),cin.tie(0);scanf("%d %d",&n,&k);int a,b,c;rep(i,1,n-1) {scanf("%d %d %d",&a,&b,&c);m[a].push_back(node(b,c));m[b].push_back(node(a,c));}dfs(1,0);printf("%d\n",dp[1][k]);return 0;
}