「Luogu P2015」二叉苹果树 解题报告

题面

一个二叉树，边数为n $(2< n\le 100)​$，每条边有一个权值，求剪枝后剩下 $p(1< p< n)​$ 条边，使 $p$ 条边的权值和最大

还看不懂？……

2   5        input:5 2        output:21
 \ /            1 3 1
  3   4            1 4 10
   \ /            2 3 20
    1            3 5 20

能理解了吧！

解题思路

树形DP

很基础的一道树形DP

对于每个点，用f[k][i]记录在以k为根的子树中，取i条枝的最大值

Warning

1、要注意叶子节点的判断

2、有可能只取一侧的子树

Code：

#include<bits/stdc++.h>
#define N 110
using namespace std;
int b[N][5],s[N];
int n,p;
int a[N][N],f[N][N];
int read()
{
    int s=0;
    char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c))
    {
        s=(s<<1)+(s<<3)+c-'0';
        c=getchar();
    }
    return s;
}
void DFS(int k,int fa)
{
    if(s[k]==1)//叶子节点直接返回
        return;
    int i,j;
    int l,r,value;
    l=r=0;
    for(i=1;i<=s[k];i++)//把l儿子和r儿子处理出来，其实不用严格区分l和r，因为效果是一样的
        if(b[k][i]!=fa)
        {
            if(!l)
                l=b[k][i];
            else
                r=b[k][i];
        }
    DFS(l,k);DFS(r,k);
    f[k][1]=max(a[k][l],a[k][r]);//
    for(i=0;i<=p-2;i++)//由于默认要选左枝和右枝，所以i要-2
    {
        f[k][i+2]=max(f[l][i+1]+a[k][l],f[r][i+1]+a[k][r]);//可能直选一边
        for(j=0;j<=i;j++)//分配左子树多少，右子树去多少枝，不用判断是否能够取满，因为取满的总是最优的
        {//不会影响
            value=f[l][j]+a[k][l]+f[r][i-j]+a[k][r];
            f[k][i+2]=max(f[k][i+2],value);
        }
    }
    return;
}
int main()
{
    int i,x,y;
    n=read();p=read();
    for(i=1;i<n;i++)
    {
        x=read(),y=read(),a[x][y]=read();//矩阵存边权
        b[x][++s[x]]=y;b[y][++s[y]]=x;//存边，由于边数不多，直接用邻接表存，不用链式前向星
    }
    DFS(1,0);//以1为根遍历数
    printf("%d",f[1][p]);//输出最后结果
    return 0;
}