前言：余于模拟赛逢此题，未AC，觉此题甚好，作此解。

题目

有 $n$ 名队员，编号为 $1$ 至 $n$。第 $i$ 名队员的优先级是 $p_i$ ，其中 $p_1,p_2,...p_n$ 是 $1$ 至 $n$ 的一个排列。优先级数值越小，越优先领取任务。

另有 $n−1$ 个不同的任务。每个任务指定两名候选队员，只能由他们中的一人领取。把队员看作顶点、任务看作连接两名候选队员的无向边，这些关系构成一棵树。

所有队员初始都没有领取任务。每名队员至多领取一个任务。你会选择一种顺序，将全部任务依次发布。每个任务发布时，按下列规则处理：

• 如果两名候选队员都没有领取任务，则由优先级数值较小的队员领取；
• 如果恰有一名候选队员没有领取任务，则由这名队员领取；
• 如果两名候选队员都已领取任务，则该任务失败。

求使所有任务都成功的发布顺序数量，答案对 $998244353$ 取模。两个顺序不同，当且仅当至少有一个发布位置上的任务不同。

当 $n=1$ 时，没有任务，空顺序视为一种成功的顺序。

输入格式

从文件 Covenant.in 中读入。

第一行包含一个正整数 $n$。

第二行包含 $n$ 个整数 $p_1,p_2,...,p_n$ 接下来 $n−1$ 行，每行包含两个整数 $u,v$，表示一个任务的两名候选队员。各行对应不同的任务。

输出格式

输出至文件 Covenant.out。

输出一行一个整数，表示使所有任务都成功的发布顺序数量对 $998244353$ 取模的结果。

样例

样例输入 1

4
2 1 3 4
1 2
2 3
3 4

样例输出 1

4

按输入顺序将三个任务记为 $e_1,e_2,e_3$ 。成功的顺序为 $(e_1,e_2,e_3)$、$(e_3,e_2,e_1)$、$(e_2,e_1,e_3)$ 和 $(e_2,e_3,e_1)$ 例如，按 $(e_3,e_1,e_2)$ 发布时，前两个任务分别由队员 $3$、$2$ 领取，第三个任务的两名候选队员均已领取任务，因而失败。

样例输入 2

5
1 2 3 4 5
1 2
1 3
1 4
1 5

样例输出 2

24

第一个发布的任务由队员 $1$ 领取，此后每个任务由对应的另一名队员领取。因此所有 $4!$ 种顺序都成功。

数据范围与提示

对于所有测试数据，

• $1\leq n\leq 2\times 10^5$，
• p 是 $1$ 至 $n$ 的排列，
• $1\leq u,v\leq n$，输入的边构成一棵树。

题解

思路是枚举最终没有领取任务的队员，也就是把他作为树根。

固定根后，每条边都必须由更靠近叶子的一端领取：根不领取任务，其余每人恰好领取一项。设 e_u 是连接 u 与其父亲的任务。若父亲的优先级数值小于 u，那么父亲优先级更高，必须先发布 e_u，再发布 u 与其孩子之间的任务，否则父亲可能抢走任务。

这些先后关系构成一个森林。森林中任务的合法发布顺序数为：

$$\frac{(n-1)!}{\prod_e siz_e},$$

其中 $siz_e$ 是任务节点在先后关系森林中的子树大小。

定义 cnt[u] 为从 u 开始、沿优先级数值严格递增的路径所能到达的节点数，包含 u 自身：

$$T_u=1+\sum_{v\sim u,\ p_v>p_u}T_v.$$

对于有向边“父亲 u 指向孩子 v”，对应的子树大小为：

$$D(u,v)= \begin{cases} T_v-T_u,&p_u>p_v,\\ T_v,&p_u<p_v. \end{cases}$$

先以任意节点为根计算一次答案，再沿树换根。注意这个根是空闲状态，领取任务时从儿子 v 到父亲 u，所以答案贡献是 $D(u,v)$。 若从 u 换到相邻节点 v，只有这条边对应的因子变化：

$$W_v=W_u\cdot D(u,v)\cdot D(v,u)^{-1}.$$

最后，只有满足 p[root] > p[neighbor] 对所有邻居成立的根才可能是空闲队员；否则根会在某条相邻任务中先领取任务。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

// 任务领取
#include <iostream>
#include <vector>
using namespace std;

const int N = 2e5 + 1023;
#define MOD 998244353
int n, p[N], rnk[N], cnt[N], inv[N], res[N], ans;
vector<int> tr[N];

#define D(u, v) (p[u] < p[v] ? cnt[v] : cnt[v] - cnt[u])

int calc_rt(int u, int fa) {
    int res = 1;
    for (int v : tr[u]) {
        if (v == fa) continue;
        res = 1ll * res * inv[D(u, v)] % MOD * calc_rt(v, u) % MOD;
    }
    return res;
}

void dfs(int u, int fa) {
    for (int v : tr[u]) {
        if (v == fa) continue;
        res[v] = 1ll * res[u] * D(u, v) % MOD * inv[D(v, u)] % MOD;
        dfs(v, u);
    }
}

int main() {
    freopen("Covenant.in", "r", stdin);
    freopen("Covenant.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        rnk[p[i]] = i;
    }
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        tr[u].push_back(v);
        tr[v].push_back(u);
    }
    for (int i = n; i >= 1; i--) {
        int u = rnk[i];
        cnt[u] = 1;
        for (int v : tr[u])
            if (p[u] < p[v])
                cnt[u] += cnt[v];
    }
    inv[1] = 1;
    for (int i = 2; i <= n; i++)
        inv[i] = MOD - 1ll * (MOD / i) * inv[MOD % i] % MOD;
    res[1] = 1;
    for (int i = 1; i < n; i++) res[1] = 1ll * res[1] * i % MOD;
    res[1] = 1ll * res[1] * calc_rt(1, 0) % MOD;
    dfs(1, 0);
    for (int u = 1; u <= n; u++) {
        bool flag = 1;
        for (int v : tr[u]) {
            if (p[u] < p[v]) {
                flag = 0;
                break;
            }
        }
        if (flag) ans = (ans + res[u]) % MOD;
    }
    cout << ans << '\n';
    return 0;
}