算法记录：树

const int MOD = 998244353;
vector<i64> f(2e5 + 1, 1), invf(2e5 + 1, 1);
i64 q_pow(i64 a, i64 b, i64 mod = LLONG_MAX)
{
    i64 res = 1;

    while (b)
    {
        if (b & 1)
        {
            res = (res * a) % mod;
        }

        a = (a * a) % mod;
        b >>= 1;
    }

    return res;
}

void mainInit()
{
    //这里O(n)去预处理阶乘和逆元阶乘，后续求组合数的时候就可以O(1)了
    for (int i = 1; i <= int(2e5); i++)
    {
        f[i] = f[i - 1] * i % MOD;
    }
    invf[int(2e5)] = q_pow(f[int(2e5)], MOD - 2, MOD);

    for (int i = int(2e5 - 1); i >= 0; i--)
    {
        invf[i] = invf[i + 1] * (i + 1) % MOD;
    }
}

void solve()
{
    int n;
    cin >> n;
    vector<int> arr(n);
    cin >> arr;
    vector<vector<int>> adj(n);
    for (int i = 0; i < n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<i64> mx(n, 0), mi(n, INT_MAX);
    vector<i64> p(n);//p[u]表示以u为根的子树满足题目要求的DFS的概率
    auto dfs = [&](auto &self, int u, int f) -> void
    {
        mi[u] = arr[u], mx[u] = arr[u];
        p[u] = 1;

        vector<pll> son;
        int k = 0;
        for (auto v : adj[u])
        {
            if (v == f)
            {
                continue;
            }

            self(self, v, u);
            k++;
            if (p[v] == 0)//如果子树不满足要求，那么以u为根的子树也不可能满足要求了
            {
                p[u] = 0;
            }
            son.push_back({mi[v], mx[v]});

            if (p[u] != 0)
            {
                p[u] = p[u] * p[v] % MOD;//乘法原理
            }
        }

        if (k == 0 || p[u] == 0)//这是叶子节点，那么就返回1就行了，或者子树不满足要求了，那么以u为根的子树也不满足要求了，直接返回就行了，返回的都是p[u]，如果是叶子节点，那么p[u]就是1，如果子树不满足要求了，那么p[u]就是0
        {
            return;
        }

        sort(son.begin(), son.end());//把子树的最小值、最大值按照从小到大排序

        if (arr[u] > son[0].first)//DFS肯定先访问树根，如果树根的值大于子树的最小值，那么就不满足题目要求了，直接返回0就行了
        {
            p[u] = 0;
            return;
        }

        for (int i = 0; i < k - 1; i++)//判断不同子树之间是否满足要求，类似不重叠子区间（允许端点重叠）
        {
            if (son[i].second > son[i + 1].first)
            {
                p[u] = 0;
                return;
            }
        }

        i64 w = 1, cnt = 1;//w是DFS遍历当前子树总的合法方案数,这里把一个子树当成一个整体来看，因为前面p[u]已经乘了每个子树的方案数了，所以这里就不需要再乘了，这里只需要考虑不同子树之间的排列方式了。

        for (int i = 1; i < k; i++)
        {
            if (son[i] == son[i - 1])//如果子树的最小值和最大值都相同，那么就说明这两个子树是一样的，相当与cnt个一样的子树进行排列，A(cnt,cnt);
            {
                cnt++;
                w = w * cnt % MOD;
            }
            else
            {
                cnt = 1;
            }
        }

        p[u] = p[u] * w % MOD * invf[k] % MOD;//p[u] * w % MOD 这部分是分子，然后本应该除以k!，但是因为我们预处理了逆元阶乘，所以就直接乘以invf[k]了，这样在逆元下就相当于除以k!了
        mx[u] = son.back().second;//然后这里记录以u为根的子树的最大值，这里为啥没去处理mi呢，因为要保证符合要求，最小值一定是每个子树本身，而最开始就把mi[u]初始化成了arr[u]了，所以就不需要再去处理了，记录子树的最大值就行了
    };

    dfs(dfs, 0, -1);
    cout << p[0] << endl;
}