重建道路

传送门

这道题对我算是意义非凡
毕竟这是我独立自主AC的第一道动规较难题

解法:

这道题想想就想到了树上背包

于是我 爽快地温习了一下树上背包 爽快地写完代码 爽快地得了72分。。。

然后我才发现
这道题tm的不是考树上背包
而是考特判

先说说背包咋写
设dp[i][j]表示第i个节点的位置删掉j个点需要次数 这个设法有点神奇。。。
因为要删n-p个点 为了方便 我把读入的p赋为n-p
树上背包的转移在此就不详细说 具体看代码
最后分离出包含根节点的树的操作数即为dp[root][p]

要特判是因为可以把子树分离出去
对于第i点的子树 要分离出p个点
就要减去子树中sz[i]-p个点 再断掉与父亲的连边
操作数就为dp[i][sz[i]-p]+1(实际上此时p为n-p 因为上面的将p赋为了n-p)

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define inf 2000000000
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dwn(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
bool vis[160];
int n,p,root,minn=inf,sz[160],par[160],dp[160][160];
struct EDGE
{
    int to,nxt;
}edge[310];
int head[160],tot=1;
void add(int u,int v)
{
    edge[++tot].to=v;
    edge[tot].nxt=head[u];
    head[u]=tot;
}
void dfs(int x)
{
    vis[x]=1,sz[x]=1;
    for(int i=head[x];i;i=edge[i].nxt)
    {
        int y=edge[i].to;
        if(vis[y]) continue;
        dfs(y);
        sz[x]+=sz[y];
    }
    vis[x]=0;
}
void get_dp(int x)
{
    vis[x]=1;
    for(int i=head[x];i;i=edge[i].nxt)
    {
        int y=edge[i].to;
        if(vis[y]) continue;
        get_dp(y);
        dwn(j,p,1)//树上背包，倒序很重要
        {
            rep(k,0,j)
            {
                dp[x][j]=min(dp[x][j],dp[x][k]+dp[y][j-k]);
            }
        }
    }
    dp[x][sz[x]]=1;
    vis[x]=0;
}
int main()
{
    scanf("%d%d",&n,&p);
    p=n-p;
    rep(i,1,n-1)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        vis[v]=1;
        par[v]=u;
        add(u,v),add(v,u);
    }
    rep(i,1,n)
    {
        if(!vis[i])
        {
            root=i;
        }
        vis[i]=0;
    }
    dfs(root);
    memset(dp,127/3,sizeof(dp));
    rep(i,1,n) dp[i][0]=0;
    get_dp(root);
    rep(i,1,n)
    {
        if(i==root) continue;
        if(sz[i]==n-p)//若 i不为根节点 这时把i子树直接分离只需一步肯定最优 其实不一定要写这个特判 下面minn操作其实包含了这种
        {
            printf("1
");
            return 0;
        }
        minn=min(minn,dp[i][sz[i]-n+p]+1);//分离子树操作
    }
    printf("%d
",min(minn,dp[root][p]));
    return 0;
}