当前位置: 代码迷 >> 综合 >> caioj 1114 树形动态规划(TreeDP)3.0:多叉苹果树【scy改编ural1018二叉苹果树】
  详细解决方案

caioj 1114 树形动态规划(TreeDP)3.0:多叉苹果树【scy改编ural1018二叉苹果树】

热度:109   发布时间:2023-09-20 19:17:37.0

一波树上背包秒杀……

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 312;
int f[MAXN][MAXN], cnt[MAXN], n, k;
struct node{ int v, w; };
vector<node> g[MAXN];void dfs(int u, int fa)
{REP(i, 0, g[u].size()){int v = g[u][i].v, w = g[u][i].w;if(v == fa) continue;dfs(v, u);cnt[u] += cnt[v];for(int j = cnt[u]; j >= 1; j--)REP(k, 1, min(cnt[v], j - 1) + 1)f[u][j] = max(f[u][j], f[u][j-k] + f[v][k] + w);}
}int main()
{scanf("%d%d", &n, &k);REP(i, 1, n){int u, v, w;scanf("%d%d%d", &u, &v, &w);g[u].push_back(node{v, w});g[v].push_back(node{u, w});cnt[i] = 1;}cnt[n] = 1;dfs(1, -1);printf("%d\n", f[1][k + 1]);return 0;
}

 

  相关解决方案