ARC121E Directed Tree
有意思的容斥加树 dp。
思路
\(a_i\) 可以是除去 \(i\) 祖先之外的所有点，考虑 \(a_i\) 的逆排列。
每一个 \(i\) 在正排列里都可以被不是自己子树内的点选择，那么逆排列里 \(i\) 不可以放自己子树内的点（不包括自己）。
现在转换求逆排列的方案数。
考虑容斥，设 \(g_i\) 为有 \(i\) 个位置不合法的方案数。
有 \(ans=\sum_{i=0}^n (-1)^ig_i(n-i)!\)。
\((n-i)!\) 有 \(n-i\) 个位置可以随便放 \(n-i\) 个数。
求 \(g_i\) 考虑树 dp，设 \(f_{u,i}\) 为 \(u\) 子树内有 \(i\) 个点不合法的方案数（只考虑不合法的点）。
因为 \(u\) 的不同子树，不合法的范围不相交，有：
\[f_{u,j+k}=f_{v,j}\times f_{v',j}
\]
\(v,v'\) 是 \(u\) 的儿子。
但这时求出来的 \(f_u\) 是 \(u\) 没选择的结果，加上 \(u\) 位置的选择：
\[f_{u,i}=f_{u,i-1}\times((sz_u-1)-(i-1))
\]
有 \(sz_u-1\) 个点可选，\(i-1\) 个点被选了。
那么 \(g_i=f_{1,i}\)。
时间复杂度 \(O(n^2)\)。
CODE
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 998244353
const int maxn=2e3+5;
int n;
int siz[maxn];
ll ans;
ll fac[maxn],f[maxn][maxn],g[maxn];
vector<int>E[maxn];
void dfs(int u)
{
f[u][0]=1,siz[u]=1;
for(auto v:E[u]) dfs(v);
for(auto v:E[u])
{
for(int i=0;i<=siz[u]+siz[v];i++) g[i]=0;
for(int i=0;i<=siz[u];i++) for(int j=0;j<=siz[v];j++) g[i+j]=(g[i+j]+f[u][i]*f[v][j]%mod)%mod;
for(int i=0;i<=siz[u]+siz[v];i++) f[u][i]=g[i];
siz[u]+=siz[v];
}
for(int i=siz[u];i>=1;i--) f[u][i]=(f[u][i]+f[u][i-1]*(siz[u]-i)%mod)%mod;
}
int main()
{
scanf("%d",&n);
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
for(int i=2;i<=n;i++)
{
int x;
scanf("%d",&x);
E[x].push_back(i);
}
dfs(1);
for(int i=0;i<=n;i++) f[1][i]=f[1][i]*fac[n-i]%mod;
for(int i=0;i<=n;i++)
{
ll k=1;
if(i&1) k=-1;
ans=(ans+k*f[1][i])%mod;
}
printf("%lld",(ans+mod)%mod);
}