G、Glass Balls

题目大意

你有一颗以为根的有向树，一共有个节点，对于每个节点初始都有一个小球，它存在的每一秒都会向父亲节点滚动一次，然后节点又分为可存储节点和不可存储节点。小球如果到了可存储节点它会掉入节点中，如果有两个小球同时掉入同一个存储节点游戏直接结束答案贡献为。否则对于起点在的小球来说，就是它在能往上滚的次数，求的期望是多少。

Solution

首先我们要找出全部存在贡献的游戏界面是什么。

我们知道任意一个节点它的全部孩子都会向上滚动到它那里去，所以对于合理的游戏局面来说，不能有任何一个节点它两个孩子都是非存储节点，那么这时候这两个孩子带来的球一定会造成崩溃。

所以对于单个节点它合理的概率就是：。即它的儿子中有个不可存储节点或者个不可存储节点的概率。因为这些点选择都是独立事件，所以整棵树构成的合理局面概率为：。

接下来考虑计算滚动次数的期望，我们知道因为它那也去不了，接下来对于它的儿子来说，就有可能往上移动一个步数，也有可能直接就是存储节点，那么我们就要计算是唯一一个合理的非存储节点的概率，其实也很容易计算，对于的父亲来说，合理局面数为，那么选为非存储节点的概率有，做一下除法就是概率了。

所以如果我们假设代表号节点小球的期望，它父亲我们叫做的话，得到下面的转移式。

对于答案来说，我们求解的是期望，如果把当作独立事件的话可以直接求和，不过能发现并不是没关系的，例如两个不同的儿子节点它们的儿子都一起上来了，这种局面下是非法的，所以要乘上总局面合理的概率来调整期望。

时间复杂度，多出来的主要是快速幂求逆元带来的。

const int MOD = 998244353, N = 5e5 + 7;
int qpow(int a, int b) {
    int res = 1;
    a %= MOD;
    for (; b; a = a * a % MOD, b >>= 1)    if (b & 1)    res = res * a % MOD;
    return res;
}
int add(int a, int b) {
    if (a + b >= MOD)    return a + b - MOD;
    return a + b;
}
int inv(int u) {
    return qpow(u, MOD - 2);
}

int p[N], fa[N], sz[N];
vector<int> G[N];
int f[N];

void dfs(int u) {
    f[u] = (1 + f[fa[u]]) * ((1 - p[1] + MOD) % MOD * p[sz[fa[u]] - 1] % MOD) % MOD * inv(add(sz[fa[u]] * (1 - p[1] + MOD) % MOD * p[sz[fa[u]] - 1] % MOD, p[sz[fa[u]]])) % MOD;
    for (auto& v : G[u]) {
        dfs(v);
    }
}

int solve() {
    int n = read(), o = read();
    p[0] = 1;
    for (int i = 1; i <= n; ++i) {
        p[i] = p[i - 1] * o % MOD;
    }
    for (int i = 2; i <= n; ++i) {
        fa[i] = read();
        G[fa[i]].emplace_back(i);
    }

    int P = 1;
    for (int i = 1; i <= n; ++i) {
        sz[i] = G[i].size();
        if (sz[i] == 0)    continue;
        P = P * add(sz[i] * (1 - o + MOD) % MOD * p[sz[i] - 1] % MOD, p[sz[i]]) % MOD;
    }

    for (auto& v : G[1])    dfs(v);

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans = add(ans, f[i]);
    }
    ans = ans * P % MOD;
    print(ans);

    return 1;
}