树状dp ural1018

时间:2024-07-07 22:06:32
#include<stdio.h>
#include<string.h>
#include <iostream>
using namespace std;
const int N=;
int dp[N][N],vis[N],head[N],num,m;
struct edge
{
int st,ed,w,next;
}e[N*];
void addedge(int x,int y,int w)
{
e[num].st=x;e[num].ed=y;e[num].w=w;e[num].next=head[x];head[x]=num++;
e[num].st=y;e[num].ed=x;e[num].w=w;e[num].next=head[y];head[y]=num++;
}
void dfs(int u)
{
vis[u]=;//标记
int i,v,w,j,k,son=;
for(i=head[u];i!=-;i=e[i].next)
{
v=e[i].ed;w=e[i].w;
if(vis[v]==)continue;
dfs(v);//自上而下,记忆化搜索
for(k=m;k>=;k--)//一共要保留m条边
{
for(j=;j<=k;j++)//在v节点的子树中选择j条边
dp[u][k]=max(dp[u][k-j]+dp[v][j-]+w,dp[u][k]);
}
}
}
int main()
{
int i,x,y,w,n;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(head,-,sizeof(head));
num=;
for(i=;i<n;i++)
{
scanf("%d%d%d",&x,&y,&w);
addedge(x,y,w);
}
memset(vis,,sizeof(vis));
memset(dp,,sizeof(dp));
dfs(); //1始终是整棵树的根
printf("%d\n",dp[][m]);
}
return ;
}