二叉苹果树

题目

Description

有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）。
这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N，树根编号一定是1。
我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝
的树：
2 5
＼／
3 4
＼／
1

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

给定需要保留的树枝数量，求出最多能留住多少苹果。注意树根不能剪没了哟。

Input

第1行2个数，N和Q(1<=Q<=N，I<N<=IOO)。
N表示树的结点数，Q表示要保留的树枝数量。
接下来N-I行描述树枝的信息。每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。每根树枝上的苹果不超过30000个。

Output

一个数，最多能留住的苹果的数量。

Sample Input

Sample Output

思路

二叉解析

一道树形dp的题目；

我们可以设dp[x][i]为以x为根的节点的儿子边（也就是i节点以下的所有边），保留了i条边；

题目是一颗二叉树所有每次我们只需考虑两个儿子的信息，然后将信息合并到根节点；

那么考虑两种情况：

1，只有一个儿子节点保留全部的边，也就是另一个儿子节点没有保留边i=0;

那么dp[x][i]=max(dp[leftx][i-1]+v[x][leftx], dp[rightx][i-1]+v[x][rightx]);

(leftx表示左儿子，rightx表示右儿子，v[][]表示两点之间的权值）；

那为什么儿子保留的边要减一dp[leftx][i-1], 因为x到leftx之间也有一条边，儿子下面的边怎么可能和父节点一样呢；

2，枚举x节点保留的边i中，分配到左边有多少条边j（j<i);

左儿子leftx保留了多少边j-1；

但是x到leftx之间也有一条边所有j要减一，那么右儿子rightx 保留边数就是i-j-1;

那么dp[x][i]=max(dp[leftx][j-1]+v[x][leftx]+dp[rightx][i-j-1]+v[x][rightx], dp[i][j]);

(leftx表示左儿子，rightx表示右儿子，v[][]表示两点之间的权值）；

那么转移方程就是

    for(ll i=1;i<=q;i++)//枚举保留边数
    for(ll j=0;j<=i;j++)//枚举分配到左边的边数
    {
                //son存的是父节点到儿子的边的编号
        ll sum=0,L=a[son[x][1]].to,R=a[son[x][2]].to;
        if(j-1>=0)//因为儿子到父节点也有条边，所以j-1才是左节点保留的边数
            sum+=a[son[x][1]].v;
        if(i-j-1>=0)//表示右边有分配
            sum+=a[son[x][2]].v;
        if(j==0)//j==0表示只分配到了右边
            dp[x][i]=max(dp[x][i],dp[R][i-1]+sum);
        else
            dp[x][i]=max(dp[x][i],dp[L][j-1]+dp[R][i-j-1]+sum);
        }

这样就好了

此题多叉情况的解析

二叉苹果树的题面(多叉情况）

代码

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
inline ll read()
{
    ll a=0,f=1; char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();}
    while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();}
    return a*f;
}//好用的快读 
ll n,q;
ll head[401],dp[401][30010],son[401][3];
struct ljj
{
    ll stb,to,v;
}a[601];
ll s=0;
inline void insert(ll x,ll y,ll z)
{
    s++;
    a[s].stb=head[x];
    a[s].to=y;
    a[s].v=z;
    head[x]=s;
}
inline void dfs(ll x,ll fa)
{
    ll tot=0;
    for(ll i=head[x];i;i=a[i].stb)
    {
        ll xx=a[i].to;
        if(xx==fa)
            continue;
        tot++;
        son[x][tot]=i;//son表示x到儿子的边（son[x][1]表示左节点的表,son[x][2]表示右节点） 
        dfs(xx,x);
    }
    if(!tot)//如果x没有节点，就返回 
        return;
    for(ll i=1;i<=q;i++)//枚举保留边数
    for(ll j=0;j<=i;j++)//枚举分配到左边的边数
    {
                //son存的是父节点到儿子的边的编号
        ll sum=0,L=a[son[x][1]].to,R=a[son[x][2]].to;
        if(j-1>=0)//因为儿子到父节点也有条边，所以j-1才是左节点保留的边数
            sum+=a[son[x][1]].v;
        if(i-j-1>=0)//表示右边有分配
            sum+=a[son[x][2]].v;
        if(j==0)//j==0表示只分配到了右边
            dp[x][i]=max(dp[x][i],dp[R][i-1]+sum);
        else
            dp[x][i]=max(dp[x][i],dp[L][j-1]+dp[R][i-j-1]+sum);
    }
}
int main()
{
    n=read();q=read();
    for(ll i=1;i<n;i++)
    {
        ll x=read(),y=read(),z=read();
        insert(x,y,z);
        insert(y,x,z);
    }
    dfs(1,0);
    printf("%lld
",dp[1][q]);
}