题目分析有nnn个人站成一排给出mmm对父子关系(a,b)(a, b)(a,b)表示bbb是aaa的父亲。要求排列中任何人都不能站在他父亲的前面。求满足条件的排列数结果对100000000710000000071000000007取模。约束条件T14T 14T14测试用例数1≤n≤400001 \leq n \leq 400001≤n≤400000≤mn0 \leq m n0≤mn每个人最多有一个父亲不存在祖先环解题思路这个问题可以转化为森林的拓扑排序计数问题。父子关系构成一个有向无环图DAG\texttt{DAG}DAG且由于每人最多一个父亲实际上形成的是多棵树森林。关键公式对于一棵有kkk个节点的有根树其拓扑排序数量为k!∏u∈treesize[u] \frac{k!}{\prod_{u \in \text{tree}} size[u]}∏u∈tree​size[u]k!​其中size[u]size[u]size[u]表示以uuu为根的子树大小。公式解释如果没有限制排列数为k!k!k!对于每个节点uuu其所有子孙在排列中必须保持uuu在它们前面的相对顺序因此要除以每个节点的子树大小扩展到森林多棵树公式变为ansn!×∏i1n1size[i](modM) ans n! \times \prod_{i1}^n \frac{1}{size[i]} \pmod{M}ansn!×i1∏n​size[i]1​(modM)算法步骤预处理计算111到400004000040000的阶乘模100000000710000000071000000007建图根据输入建立父子关系图标记根节点没有父亲的节点即为树的根计算子树大小从每个根节点开始执行DFS\texttt{DFS}DFS计算每个节点的sizesizesize计算结果应用上述公式使用模逆元处理除法输出对每个测试用例输出结果参考代码// Stand in a Line// UVa ID: 11174// Verdict: Accepted// Submission Date: 2025-11-01// UVa Run Time: 0.080s//// 版权所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMOD1000000007;constintMAXN40005;longlongfact[MAXN];vectorintchildren[MAXN];intsz[MAXN];boolhasParent[MAXN];longlongmodPow(longlonga,longlongb){longlongres1;while(b0){if(b1)resres*a%MOD;aa*a%MOD;b1;}returnres;}voiddfs(intu){sz[u]1;for(intv:children[u]){dfs(v);sz[u]sz[v];}}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);fact[0]1;for(inti1;iMAXN;i)fact[i]fact[i-1]*i%MOD;intT;cinT;while(T--){intn,m;cinnm;for(inti1;in;i){children[i].clear();hasParent[i]false;}for(inti0;im;i){inta,b;cinab;children[b].push_back(a);hasParent[a]true;}for(inti1;in;i)if(!hasParent[i])dfs(i);longlongrfact[n];for(inti1;in;i){rr*modPow(sz[i],MOD-2)%MOD;}coutr\n;}return0;}