自动搬运

查看原文

来自洛谷，原作者为

	Mirasycle 遗憾离场

搬运于2025-08-24 23:17:01，当前版本为作者最后更新于2025-05-31 19:11:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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;
}