洛谷2015 二叉苹果树

时隔半年再来做发现还是不会，于是乎还是写个总结吧。

题意

一棵二叉树，只能保留 $Q$ 条边，求剩下的边最大边权和。

其中点数 $N\le 100$ ，$Q\le 100$ 。

题解

用 $f[x][j]$ 表示在以 $x$ 为根的子树上保留 $j$ 条边的最优情况。

搜索时枚举 $x$ 的子节点 $y$ ，然后类比背包枚举以 $y$ 为根的子树保留的边数 $k$ ，得到状态转移如下：

$f[x][j]=max(f[x][j],f[y][k]+f[x][j-k-1]+dis[x][y])$

$j-k-1$ 的原因是 $x$ 与 $y$ 之间的边要保留。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    int next,to,w;
} edge[205];
int cnt,head[105],n,m,a,b,c,f[105][105],siz[105];

inline void add(int u,int v,int w)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(int x,int fa)
{
    siz[x]=1;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to,w=edge[i].w;
        if (y==fa) continue;
        dfs(y,x);
        siz[x]+=siz[y];
        for (int j=min(m,siz[x]);j;j--)
            for (int k=min(j-1,siz[y]);k>=0;k--)
                f[x][j]=max(f[x][j],f[x][j-k-1]+f[y][k]+w);
    }
}

int main()
{
    n=read(); m=read();
    for (int i=1;i<n;i++)
    {
        a=read(); b=read(); c=read();
        add(a,b,c);
        add(b,a,c);
    }
    dfs(1,0);
    printf("%d",f[1][m]);
    return 0;
}