【题解】Partial Virtual Trees

· · 题解

题面：Partial Virtual Trees

首先发现是真子集的限制，考虑使限制变为子集的限制。考虑答案数组 ans，限制变为子集限制的数组 f，那么 f_n=\sum_{i=1}^nans_i\times C_n^i，即考虑枚举哪些次数是真正操作了的，易得这个等式。如果我们已经求出了 f 数组，反推 ans 数组，只要移项就好了。即 ans_n=f_n-\sum_{i=1}^{n-1}ans_i\times C_n^i。

对于求 f，我们可以考虑树形 dp。具体地，设 F_{u,i} 恰好在第 i 次操作后删完了 u 子树内的元素的方案数。特别地，对于 F_{1,i}，表示删完了除 1 以外的元素的方案数。

对于 u\neq 1 的转移，考虑两种情况：

为什么考虑这两种情况？对于 u，只有当其的两个不同的子树内有元素时 u 才会被作为 LCA。

那么转移方程有：

  1. F_{u,i}\leftarrow \prod_{v\in son_u}\sum_{j=1}^iF_{v,j}
  2. F_{u,i}\leftarrow \sum_{del=1}^{i-1}\sum_{v\in son_u}F_{v,i}\prod_{w\in son_u,w\neq v}\sum_{t=1}^{del}F_{w,t}

其中，son_u 表示 u 的儿子集合，del 枚举的是 u 删除的时间。直接做肯定超时，考虑优化。对于方程 1，对于 F_v 做前缀和即可。对于方程 2，将 \sum_{del} 提到 F_{v,i} 以后，这样 \prod_{w\in son_u,w\neq v}\sum_{t=1}^{del}F_{w,t} 可以前缀和优化+前后缀合并优化，并对 \sum_{del} 做前缀和，然后就解决了。

再看 u=1 的转移方程，其实相当于只用 转移 1 就好了。怎么理解？因为我们相当于把 1 的子树在 i 的时间以内删掉，而我们是子集操作，所以允许最后有若干个时刻是不动的。

求出了 F 数组，那么 f_i=F_{1,i}，再求出 ans 数组即可。

code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N=2e3+10;
LL n,P,f[N][N],pre[N],suf[N],g[N][N],sum[N][N];
vector<LL> e[N];
void dfs(LL u,LL fa)
{
    vector<LL> son;
    for(auto v:e[u]) if(v!=fa)
        dfs(v,u),son.push_back(v);
    for(int i=1;i<n;i++)
    {
        pre[0]=1; suf[son.size()+1]=1;
        for(int j=1;j<=son.size();j++) pre[j]=pre[j-1]*sum[son[j-1]][i]%P;
        for(int j=son.size();j>=1;j--) suf[j]=suf[j+1]*sum[son[j-1]][i]%P;
        for(int j=1;j<=son.size();j++) g[j][i]=(pre[j-1]*suf[j+1]%P+g[j][i-1])%P;
    }
    for(int i=1;i<n;i++)
    {
        f[u][i]=1;
        for(auto v:son) f[u][i]=f[u][i]*sum[v][i]%P;
        if(u!=1) for(int j=1;j<=son.size();j++)
            f[u][i]=(f[u][i]+f[son[j-1]][i]*g[j][i-1]%P)%P;
        sum[u][i]=(sum[u][i-1]+f[u][i])%P;
    }
}
int main()
{
    scanf("%lld%lld",&n,&P);
    for(int i=1;i<n;i++)
    {
        LL u,v;
        scanf("%lld%lld",&u,&v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
    for(int i=0;i<=n;i++)
        for(int j=0;j<=i;j++)
            if(j==0||j==i) sum[i][j]=1;
            else sum[i][j]=(sum[i-1][j-1]+sum[i-1][j])%P;
    pre[0]=0;
    for(int i=1;i<n;i++)
    {
        pre[i]=f[1][i];
        for(int j=1;j<i;j++) pre[i]=(pre[i]-sum[i][j]*pre[j]%P+P)%P;
        printf("%lld ",pre[i]);
    }
    return 0;
}