Solution - Atcoder ARC150D Removing Gacha

考虑到每次操作都比定会选上一个点，于是答案可以表示为每个点被选中的次数之和。
即令 \(c_i\) 为 \(i\) 点被选中的次数，答案即为 \(E(\sum\limits_{i = 1}^n c_i)\)。

根据期望的线性性，考虑把答案的 \(E\) 拆到每个 \(c_i\) 上，即变为 \(\sum\limits_{i = 1}^n E(c_i)\) 的形式。

那么对于每个点 \(i\) 就很好的独立开了。
考虑到因为这个选取点是仅与其祖先有关的，所以可以考虑用深度 \(d = \operatorname{dep}_i\) 来表示其对应的期望次数。
即令 \(f_d\) 为深度为 \(d\)（一条长为 \(d\) 的链）的点期望被选取的次数，把答案转为 \(\sum\limits_{i = 1}^{n} f_{\operatorname{dep}_i}\)。

接下来考虑求解 \(f_d\)。
因为这里是均匀随机的去做，所以对于包括其祖先的这 \(d\) 个点的被选中的期望次数应该是相同的。
所以考虑转为总共期望多少次能够把 \(d\) 个点都选中。
这个可以考虑已经选中了 \(i\) 个点，那么下一次选中一个未被选中的点的概率就是 \(\frac{d - i}{d}\)，对应的期望次数就是 \(\frac{d}{d - i}\)。
所以总的期望次数就是 \(\sum\limits_{i = 0}^{d - 1} \frac{d}{d - i} = \sum\limits_{i = 1}^d \frac{d}{i} = d\times \sum\limits_{i = 1}^d \frac{1}{d}\)。
所以有 \(f_d = \dfrac{d\times \sum\limits_{i = 1}^d \frac{1}{d}}{d} = \sum\limits_{i = 1}^d \frac{1}{d}\)。

时间复杂度 \(\mathcal{O}(n)\)。

#include<bits/stdc++.h>
using ll = long long;
constexpr ll mod = 998244353;
const int maxn = 2e5 + 10;
ll inv[maxn], f[maxn];
int fa[maxn], dep[maxn];
int main() {
   int n; scanf("%d", &n);
   dep[1] = 1;
   for (int i = 2; i <= n; i++) {
      scanf("%d", &fa[i]);
      dep[i] = dep[fa[i]] + 1;
   }
   inv[0] = inv[1] = 1ll;
   for (int i = 2; i <= n; i++)
      inv[i] = inv[mod % i] * (mod - mod / i) % mod;
   for (int i = 1; i <= n; i++)
      f[i] = (f[i - 1] + inv[i]) % mod;
   ll ans = 0;
   for (int i = 1; i <= n; i++)
      (ans += f[dep[i]]) %= mod;
   printf("%lld\n", ans);
   return 0;
}