P8917 [DMOI-R2] 风神瞳（Aeolus Hitomi）

比较裸的树上背包。

最需要处理的就是向叶子节点连续跳 $k$ 步。设计状态 $f_{x,t,i}$ 为从 $x$ 还需要向叶子节点跳 $t$ 步并且收集 $i$ 个风神瞳最少花费。

考虑如何转移。因为这 $t$ 步只能跳一次，转移过程中我们令 $f_{x,t,i}$ 已经使用了这 $t$ 步。而对于子节点 $y$：

1.在 $y$ 上跳这 $t$ 步，那么相当于 $x$ 在之前的子树上需要跳 $0$ 步：$f_{x,t,i}\gets f_{x,0,i-j}+f_{y,t-1,j}+1$。

2.在之前的子树上跳了这 $t$ 步，那么相当 $x$ 在 $y$ 上需要跳 $0$ 步。而我们可以选择直接走到 $y$，或者先向上走 $\le \min {dep_x-1,k}$ 步，再向叶子结点跳 $k$ 步：$f_{x,t,i}\gets f_{x,t,i-j}+ \min {f_{y,0,j}+2,\min_{p=\max {k-dep_x+1,1}}^{k}{k-p+1+f_{y,p-1,j}+1 }}$，后面的式子是一个整体，拿出来单独计算即可。

对于 $t=0$ 单独处理，类似上面的转移。时间复杂度 $\mathcal O(nmk)$。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e3+10,M=5e2+10,K=1e2+10,INF=1e9;
template<class T>
inline void read(T &x)
{
    x=0;int f=0; 
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,m,p,q;
int tot,head[N],ver[N<<1],ne[N<<1];
int a[N],si[N],d[N];
int f[N][K][M],ans[N<<1];
inline void add(int u,int v)
{
    ver[++tot]=v;
    ne[tot]=head[u];
    head[u]=tot;
}
void dfs(int x,int fa)
{
    si[x]=a[x];
    f[x][0][a[x]]=0;
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa)continue;
        d[y]=d[x]+1;
        dfs(y,x);
        for(int j=si[x]+si[y];~j;j--)
            for(int k=max(j-si[x],0);k<=si[y];k++)
            {
                int res=INF;
                for(int t=max(p-d[x],1);t<=p;t++)
                    res=min(res,(p-t+1)+f[y][t-1][k]+1);
                res=min(res,f[y][0][k]+2);
                for(int t=1;t<=p-1;t++)
                    f[x][t][j]=min({f[x][t][j],f[x][0][j-k]+1+f[y][t-1][k],f[x][t][j-k]+res});
                f[x][0][j]=min(f[x][0][j],f[x][0][j-k]+res);
            }
        si[x]+=si[y];
    }
}
int main()
{
    read(n,m,p,q);
    for(int i=1;i<n;i++)
    {
        int u,v;
        read(u,v);
        add(u,v),add(v,u);
    }
    for(int i=1;i<=m;i++)
    {
        int x;
        read(x);
        a[x]=1;
    }
    memset(f,0x3f,sizeof(f));    
    dfs(1,0);
    f[1][0][m+1]=2*n;
    for(int i=0;i<=m;i++)
        for(int j=f[1][0][i];j<f[1][0][i+1];j++)
            ans[j]=i;
    while(q--)
    {
        int x;
        read(x);
        if(x>=2*n)
        {
            printf("%d\n",m);
            continue;
        }
        printf("%d\n",ans[x]);
    }
    return 0;
}