题解：P12639 [UOI 2020] Topological Sorting of a Tree

· · 题解

UOI 怎么考板子题？？经典树上拓扑序容斥。

将填入数字看成拓扑序，如果全部都是 < 的话很好办，那就是外向树拓扑序个数，为 \dfrac{n!}{\prod size_u}。

现在我们多了内向边，于是需要把他们容斥掉。假设钦定了 c 条符号为 > 的边不满足性质（变成了 < 号的边），那么就有 (-1)^c 的系数。这样子最后会形成一个森林，一颗树的内部有拓扑序要求，树和树之间无要求。合并两颗大小分别为 n 和 m 的树的方案数为将排名 [1,2\dots n] 和排名 [1,2\dots m] 整合到排名 [1,2\dots n+m] 的方案数，你只需要在这 n+m 个位置中选 n 个位置依次填入原排名为 1,2\dots n 的数即可，那么就是 {n+m\choose n}。

考虑带着容斥系数进行 dp，每钦定一条边就 \times (-1)。

由于贡献系数是和子树大小相关的，所以我们要在 dp 的时候记录当前联通块的大小。所有设 f_{u,i} 表示在 u 点的时候其所在联通块大小为 i 的时候的带着容斥系数的方案数之和。根据拓扑序公式，每次遇到一个大小为 i 的子树都要乘上 \dfrac{1}{i} 的贡献，这个我们放在最后乘，下面的转移式子中不讨论这一项。

在遇到 < 的时候，就是 \dfrac{n!}{\prod sz_i} 和 \dfrac{m!}{\prod sz_i} 变成 \dfrac{(n+m)!}{\prod sz_i}，我们发现这个变化恰好是 \dfrac{(n+m)!}{n!\times m!}={n+m\choose n}。

f_{u,i+j}\gets f_{u,i}\times f_{v,j}\times {sz_u+sz_v\choose sz_u}

在遇到 > 的时候，可以选择不钦定那么就是任意顺序，是森林的合并，有系数 {sz_u+sz_v\choose sz_u}，或者钦定为 <，和第一个转移系数相同就是多了一个 -1。

f_{u,i+j}\gets -f_{u,i}\times f_{v,j}\times {sz_u+sz_v\choose sz_u} f_{u,i}\gets f_{u,i}\times f_{v,j}\times {sz_u+sz_v\choose sz_u}

注意每次做完转移之后要 f_{u,i}\gets f_{u,i}\times \dfrac{1}{i}。

时间复杂度 O(n^2)。

#include<bits/stdc++.h>
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
const int maxn=3e3+10;
const int mod=1e9+7;
void add(int &x,int y){ x=x+y>=mod?x+y-mod:x+y; }
void sub(int &x,int y){ x=x<y?x-y+mod:x-y; }
vector<pair<int,int> > G[maxn]; 
int n,f[maxn][maxn],g[maxn],sz[maxn];
int C[maxn][maxn],inv[maxn],fac[maxn];
void dfs(int u,int fa){
    f[u][1]=1; sz[u]=1;
    for(auto z:G[u]){
        int v=z.fi,w=z.se;
        dfs(v,u);
        if(w){
            for(int i=1;i<=sz[u];i++)
                for(int j=1;j<=sz[v];j++)
                    add(g[i+j],1ll*f[u][i]*f[v][j]%mod*C[sz[u]+sz[v]][sz[u]]%mod);
        }else{
            for(int i=1;i<=sz[u];i++)
                for(int j=1;j<=sz[v];j++){
                    sub(g[i+j],1ll*f[u][i]*f[v][j]%mod*C[sz[u]+sz[v]][sz[u]]%mod);
                    add(g[i],1ll*f[u][i]*f[v][j]%mod*C[sz[u]+sz[v]][sz[u]]%mod);
                }
        }
        sz[u]+=sz[v];
        for(int i=1;i<=sz[u];i++) f[u][i]=g[i],g[i]=0;
    }
    for(int i=1;i<=sz[u];i++) f[u][i]=1ll*f[u][i]*inv[i]%mod;
}
void init(){
    inv[1]=fac[0]=1; C[0][0]=1;
    for(int i=1;i<=n;i++) fac[i]=1ll*i*fac[i-1]%mod;
    for(int i=2;i<=n;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    for(int i=1;i<=n;i++){
        C[i][0]=1;
        for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n; init();
    for(int v=2;v<=n;v++){
        int u,t=0; char ch;
        cin>>u>>ch; t^=(ch=='<');
        G[u].pb(v,t);
    }
    dfs(1,0); int ans=0;
    for(int i=1;i<=n;i++) add(ans,f[1][i]);
    cout<<ans<<endl;    
    return 0;
}