luogu2015 二叉苹果树

 

1. 题目

   【题目描述】 有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）

   这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。

   我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树

    2    5
     \  / 
       3    4
         \  /
           1

   现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。

   给定需要保留的树枝数量，求出最多能留住多少苹果。

   【输入格式】

   第1行2个数，N和Q(1<=Q<= N,1<N<=100)。

   N表示树的结点数，Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。

   每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。

   每根树枝上的苹果不超过30000个。

   【输出格式】 一个数，最多能留住的苹果的数量。

   【代码】

/*
User:Mandy.H.Y
Language:c++
Problem:appletree
*/ 

#include<bits/stdc++.h>

#define Max(x,y) (x)>(y)?(x):(y)
#define Min(x,y) (x)<(y)?(x):(y)
#define mem(A) memset((A),0,sizeof(A))

const int maxn=102;

int n,q,first[maxn],size=0,f[maxn][maxn];

struct Edge
{
    int v,w,nt;
}edge[maxn<<1];

template<typename T>inline void read(T &x)
{
    x=0;char c=getchar();bool f=0;
    while(c<'0'||c>'9') {f|=(c=='-');c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+(c^48); c=getchar();}
    if(f)x=-x;
}

template<typename T>void putch(const T x)
{
    if(x>9) putch(x/10);
    putchar((x%10)|48);
}

template<typename T>inline void put(const T x)
{
    if(x<0) putchar('-'),putch(-x);
    else putch(x);
}

void docu()
{
    freopen("appletree.txt","r",stdin);
}

void eadd(int u,int v,int w)
{
    edge[++size].v=v;
    edge[size].w=w;
    edge[size].nt=first[u];
    first[u]=size;
}

void readdata()
{
    read(n);read(q);
    for(int i=1;i<n;++i)
    {
        int x,y,z;
        read(x);read(y);read(z);
        eadd(x,y,z);
        eadd(y,x,z);
    }
}

int dp(int u,int fa,int num,int ww)
{
    if(num<=0) return 0;
    if(f[u][num]) return f[u][num];
    int v[3],j=0,w[3];
    f[u][num]+=ww;
    if(num==1) return f[u][num];
    for(int i=first[u];i;i=edge[i].nt)
    {
        int v1=edge[i].v,w1=edge[i].w;
        if(v1==fa) continue;
        v[++j]=v1;
        w[j]=w1;
    }
    if(j==0) return f[u][num];
    for(int j=0;j<num;++j)
    {
        f[u][num]=Max(f[u][num],ww+dp(v[2],u,num-j-1,w[2])+dp(v[1],u,j,w[1]));
    }
    return f[u][num];
}

void work()
{
    put(dp(1,0,q+1,0));
}

int main()
{
//  docu();
    readdata();
    work();
    return  0;
}