求限定子树数量的二叉树的最大子树和

Question

给一棵二叉树，给一个非0 integer K，K代表选取相连的K个节点，求K个子节点组成和最大的子树

比如这张图，在K为5的情况下，最大子树是3，4，8，10，2

Answer 1

树dp。dp[i][j]表示以第i号节点为根、大小为j的连通子图（这里不能称为子树，故称连通子图）的最大权值和。那么有dp[i][j]=max(dp[lson[i]][p]+dp[rson[i]][j-1-p]),0<=p<=j-1。
题目要选的大小为k的连通子图必然以某一点为根，所以，dp[i][k]（1<=i<=n）的最大值即为答案。
代码如下

 #include<bits/stdc++.h>
using namespace std;

const int N=10010;
const int INF=0x3f3f3f3f;
int son[N][2],n,k;
int val[N],dp[N][110],choose[N][110];
void dfs(int x)
{
    if(!x)return;
    dfs(son[x][0]);
    dfs(son[x][1]);
    dp[x][0]=0;
    for(int i=1;i<=k;i++)
    {
        dp[x][i]=-INF;
        for(int j=0;j<i;j++)
        {
            if(dp[son[x][0]][j]+val[x]+dp[son[x][1]][i-j-1]>dp[x][i])
            {
                dp[x][i]=dp[son[x][0]][j]+val[x]+dp[son[x][1]][i-j-1];
                choose[x][i]=j;
            }
        }
    }
}

void dfs1(int x,int nb)
{
    if(!nb)return;
    printf("%d %d\n",x,val[x]);
    dfs1(son[x][0],choose[x][nb]);
    dfs1(son[x][1],nb-1-choose[x][nb]);
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",val+i);//read the value on each node
    for(int i=1;i<=n;i++)scanf("%d%d",&son[i][0],&son[i][1]);//read the id of each node's sons, 0 for not having this son
    for(int i=1;i<=k;i++)dp[0][i]=-INF;
    dp[0][0]=0;
    dfs(1);
    int ans=-INF,flg=0;
    for(int i=1;i<=n;i++)
    {
        if(dp[i][k]>ans)
        {
            ans=dp[i][k];
            flg=i;
        }
    }
    printf("%d\n",ans);//the max sum
    dfs1(flg,k);
    return 0;
}
/*
9 5
2 3 5 4 8 3 6 10 2
2 3
4 5
6 7
8 9
0 0
0 0
0 0
0 0
0 0
*/