树状dp ural1018

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