一道树形dp入门题,先放代码后面补。
#include <bits/stdc++.h>
using namespace std;
const int N = 210;
int head[N], tot, dp[N][N];
struct Edge{
int v, w, next;
}edge[N];
int n, q;
void add(int u, int v, int w){
edge[tot].v = v;
edge[tot].w = w;
edge[tot].next = head[u];
head[u] = tot ++;
}
void dfs(int now, int pre){
for(int i = head[now]; i != -1; i = edge[i].next){
int v = edge[i].v;
if(v == pre)
continue;
dfs(v, now);
for(int j = q; j >= 0; j --)
for(int k = 0; k < j; k ++)
dp[now][j] = max(dp[now][j], dp[now][k] + dp[v][j - k - 1] + edge[i].w);
}
}
int main(){
cin >> n >> q;
memset(head, -1, sizeof head);
for(int i = 1; i <= n - 1; i ++){
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
add(v, u, w);
}
dfs(1, 0);
cout << dp[1][q] << endl;
return 0;
}