期望步数

G-Glass Ball

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include <sstream>
#include<map>
using namespace std;
//#define int long long
#define ll long long
typedef pair<int, int> PII;
const int N = 5e5 + 10;
const int MOD = 998244353;
int dp[N];
int siz[N];
int n;
int p;
int pan = 1;
vector<int> g[N];
int qmi(int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b & 1) {
            res = 1ll*res * a % MOD;
        }
        a = 1ll*a * a % MOD;
        b = b >> 1;
    }
    return res;
}
void dfs(int fa) {
    pan = 1ll * pan * (( 1ll * siz[fa] * (1 - p + MOD) % MOD * qmi(p, siz[fa] - 1) % MOD + qmi(p, siz[fa])) % MOD) % MOD;
    for (int i : g[fa]) {
        dp[i] = 1ll * (1 + dp[fa]) * (1 - p + MOD) % MOD * qmi(p, siz[fa] - 1) % MOD * qmi(1ll * siz[fa] * (1 - p + MOD) % MOD * qmi(p, siz[fa] - 1) % MOD + qmi(p, siz[fa]),MOD-2) % MOD;
        if (g[i].size() > 0)dfs(i);
    }
    return;
}
int main() {
    cin >> n;
    cin >> p;
    int root = 1;
    for (int i = 2; i <= n; i++) {
        int a;
        cin >> a;
        g[a].push_back(i);
        siz[a]++;
    }
    dp[root] = 0;
    dfs(root);
    int ans = 0;
    for (int i = 2; i <= n; i++) {
        ans = (ans + dp[i]) % MOD;
    }
    ans = 1ll*ans * pan % MOD;
    cout << ans << "\n";
    return 0;
}

细节

注意取模操作，装换long long 操作