题解：AT_agc079_a [AGC079A] Tree Contraction Sequence

TrueGod · 2026-11-11 08:16:37 · 题解

操作的过程太过复杂，考虑将题面简化。

发掘一下性质，如果想让一种删除方案合法，那么任何时刻对于每个结点 u 其所对应的序列都必须是连续的，所以我们可以用一个区间 [u,r_u] 来表示 u 对应的序列。那么在删除结点 v 时，我们要求其父亲 u 满足 r_u=v-1，此时我们知道 (u,r_u] 范围内的结点已经全部被删除，也就是说，在删除 v 之前，我们必须先删除所有满足 u\lt x\lt v 的点 x。更进一步，我们发现这个条件就等价于 p_v\lt x\lt v。

容易发现这个条件是充要的。现在对于每个 u，我们要求 p_u\lt x\lt u 的 x 要先被删除，这是经典问题。让所有 x 向 u 连边就变为拓扑序计数。但是一般 DAG 的拓扑序计数是 NPC 问题，考虑优化图的结构。

注意到对于 x 可以只保留出边编号最小的边，且不会影响拓扑关系。简单证明一下，设 x 的编号最小出边为 \text{out}(x)，对于所有 x 在原图上的出边 u，都有 p_u\le x\le \text{out}(x)\le u，若 u=\text{out}(x) 就已经连了这条边，否则一直令 x\gets \text{out}(x) 一定能到达 u。而很显然，DAG 的反图不会改变拓扑序，且这张 DAG 的反图每个点的入度最多为 1，所以变成了一个森林。

建图过程可以使用单调栈实现，问题转化为树上拓扑序计数，可以在 \mathcal{O}(n) 的时间内解决。具体地，设 f_u 表示 u 子树内的拓扑序数，则有

#include<bits/stdc++.h>
using namespace std;using ll=long long;const int N=250005,mod=998244353;
ll T,n,p[N],fa[N],f[N],sz[N],fac[N],inv[N];vector<int>G[N];
ll pw(ll n,ll m,ll p){ll res=1;while(m){if(m&1)res=res*n%p;n=n*n%p,m>>=1;}return res;}
void dfs(int u){sz[u]=f[u]=1;for(int v:G[u])dfs(v),sz[u]+=sz[v],f[u]=f[u]*f[v]%mod*inv[sz[v]]%mod;f[u]=f[u]*fac[sz[u]-1]%mod;}
main(){
    fac[0]=1;for(int i=1;i<=250000;i++)fac[i]=fac[i-1]*i%mod;
    inv[250000]=pw(fac[250000],mod-2,mod);for(int i=249999;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
    for(cin>>T;T--;) {
        vector<int>s;cin>>n;for(int i=1;i<=n;i++)G[i].clear();for(int i=2;i<=n;i++)cin>>p[i],fa[i]=1;
        for(int i=n;i>=2;i--){while(s.size()&&p[s.back()]>=i)s.pop_back();if(s.size())fa[i]=s.back();s.push_back(i);}
        for(int i=2;i<=n;i++)G[fa[i]].push_back(i);dfs(1);cout<<f[1]<<'\n';
    }
}