专栏首页wymP2015 二叉苹果树 树状dp

P2015 二叉苹果树 树状dp

P2015 二叉苹果树

#include <bits/stdc++.h>
using namespace std;
int dp[101][101]; 
int mp[1001][1001];
struct NO{
	int w,to,nxt;
}no[501];
int cnt,sid[101];
int head[101];
int q,n;
int book[101];
void add(int u,int v,int w){
	++cnt;
	no[cnt].to = v; no[cnt].w = w;
	no[cnt].nxt = head[u];
	head[u] = cnt;
}	
void dfs(int u,int fa){
	for(int l=head[u];l;l=no[l].nxt){
		int v = no[l].to; 
		if(v==fa)continue;
		dfs(v,u);  sid[u]+=sid[v]+1;
		for(int i=min(sid[u],q);i>0;i--)
			for(int j=min(sid[v],i-1);j>=0;j--){
				dp[u][i] = max(dp[u][i],dp[u][i-j-1]+dp[v][j]+no[l].w);
			}
	}
}
int main()
{

	scanf("%d %d",&n,&q);
	memset(head,0,sizeof(head));
	for(int i=0;i<n-1;i++)
		{
			int u,v,w;
			scanf("%d %d %d",&u,&v,&w);
			add(u,v,w); add(v,u,w);
		}
	dfs(1,-1);
	printf("%d\n",dp[1][q]);
	return 0;
 } 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU 1878 欧拉回路

    #include <bits/stdc++.h> using namespace std; const int N=1005; int in[N]; i...

    用户2965768
  • 区间更新与点值

    用户2965768
  • Educational Codeforces Round 67 (Rated for Div. 2) A~E 贪心,构造,线段树,树的子树

    Educational Codeforces Round 67 (Rated for Div. 2)

    用户2965768
  • P1036 选数

    用户7727433
  • AtCoder Beginner Contest 177 A ~ E

    C 思路:数据范围比较大,O(n^n)的复杂度肯定不可以,那么我们要分析式子 假设有一组数据:

    用户7727433
  • 2013年第四届蓝桥杯C/C++B组省赛题目解析

    Zoctopus
  • BUPT2017 wintertraining(15) #2 题解

    ​ 因为2520%pre_lcm0,所以x%pre_lcm(x%2520)%pre_lcm

    饶文津
  • 【USACO 3.2】Sweet Butter(最短路)

    枚举到的某点,然后优先队列优化的dijkstra求最短路,把给定的点到其的最短路加起来,更新最小值。复杂度是

    饶文津
  • HDU 1878 欧拉回路

    #include <bits/stdc++.h> using namespace std; const int N=1005; int in[N]; i...

    用户2965768
  • LeetCode Weekly Contest 31解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447

扫码关注云+社区

领取腾讯云代金券