题解--茎

abruce · 2022-12-19 15:34:33 · 题解

目前已改正为 O(n^2)，数据有可能之后会加强。

在正解中，我们先求出 f_{u,k} 表示 u 子树内进行了 k 次操作的方案，树形背包即可，这部分 O(n^2)。同时我们也解决了 k=1 或 x=1。
考虑到钦定 x 操作位置会影响其所有祖先选择，可以想到把祖先和他们的其它子树分开，但这样具有后效性（因为难以保证 u 的子树的操作都在 u 之前），所以我们考虑从根进行二次 dp。
首先，我们把 1 到 x 这条链称为“茎”，和题目描述一样。
设 g_{u,k} 为当前茎从根选到了 u，剩余 k 操作给茎 u 后面的点留着，这些操作有相对顺序但并未被实际放在操作序列的某一个位置上。最终答案就是 g_{x,k-1} （强制钦定到达 x 时 k 这个位置 dp 值不能拷贝过来即可）。
考虑转移，当从 fa 转移到 u 时，我们先考虑 u 选不选。如果不选，直接拷贝，否则设它和父亲之间填了 p 个操作，从 g_{fa,k} 转移过来的话，那么操作序列就必须按顺序填 fa 给他留的 p 个操作。所以转移到 g_{u,k-p}，可以通过一个前缀和优化做到单次 O(n)，总共 O(n^2)。
接下来我们考虑把 u 不在茎上的子树的操作填进去，不难发现这些操作都是给后面留的，于是背包一下即可。复杂度分析可以看做一棵以 x 为根的树做树形背包，复杂度 O(n^2)。
综上，我们在 O(n^2) 的时间通过了本题。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}
namespace tokidosaya {
    const int maxn=505,mod=1e9+7;
    struct edge {
        int next,to;
    } e[maxn*2];
    int h[maxn],cnt,n,k,X,d[maxn],ff[maxn],siz[maxn],now,zc[maxn],o;
    ll f[maxn][maxn],ans,fac[maxn],inv[maxn],g[2][maxn],w[maxn];
    void addedge(int x,int y) {
        e[++cnt].next=h[x],e[cnt].to=y,h[x]=cnt;
    }
    ll qpow(ll x,int y) {
        ll w=1;
        while(y) {
            if(y&1)w=w*x%mod;
            x=x*x%mod,y>>=1;
        }
        return w;
    }
    ll C(int x,int y) {
        if(y>x||y<0)return 0;
        return fac[x]*inv[x-y]%mod*inv[y]%mod;
    }
    void dfs(int u,int fa) {
        ff[u]=fa,f[u][0]=1;
        for(int i=h[u]; i; i=e[i].next) {
            int v=e[i].to;
            if(v==fa)continue;
            dfs(v,u);
            for(int j=siz[u]; j>=0; j--)
                for(int k=siz[v]; k; k--)f[u][j+k]=(f[u][j+k]+f[u][j]*f[v][k]%mod*C(j+k,k))%mod;
            siz[u]+=siz[v];
        }
        for(int i=siz[u]; i>=0; i--)f[u][i+1]=(f[u][i+1]+f[u][i])%mod;
        siz[u]++;
    }
    int getw(int u) {
        int nc=0;
        memset(w,0,sizeof(w)),w[0]=1;
        for(int i=h[u]; i; i=e[i].next) {
            int v=e[i].to;
            if(d[v])continue;
            for(int j=nc; j>=0; j--)
                for(int k=siz[v]; k; k--)w[j+k]=(w[j+k]+w[j]*f[v][k]%mod*C(j+k,k))%mod;
            nc+=siz[v];
        }
        return nc;
    }//这个相当于把不在茎上的子树合并进去
    int main() {
        int x,y;
        n=read(),k=read(),X=read(),fac[0]=1;
        for(int i=1; i<=n; i++)fac[i]=fac[i-1]*i%mod;
        inv[n]=qpow(fac[n],mod-2);
        for(int i=n; i; i--)inv[i-1]=inv[i]*i%mod;
        for(int i=1; i<n; i++) {
            x=read(),y=read();
            addedge(x,y),addedge(y,x);
        }
        dfs(1,0),x=X;
        while(x)d[x]=1,zc[++o]=x,x=ff[x];
        reverse(zc+1,zc+o+1),getw(1);
        for(int i=0; i<n; i++)g[1][i]=w[i];
        for(int i=2; i<=o; i++) {
            int now=i&1,lst=now^1,u=zc[i],nc=getw(u);
            memcpy(g[now],g[lst],sizeof(g[now]));
            ll sum=0;
            for(int j=n-1; j>=0; j--) {
                sum=(sum+g[now][j])%mod;
                if(i==o)g[now][j]=0;
                g[now][j]=(g[now][j]+sum)%mod;
            }
            for(int j=n-1; j>=0; j--)
                if(g[lst][j])for(int k=nc; k; k--)g[now][j+k]=(g[now][j+k]+g[now][j]*w[k]%mod*C(j+k,k))%mod;
        }
        printf("%lld",g[o&1][k-1]);
        return 0;
    }
}
int main() {
    return tokidosaya::main();
}