题意
给定一棵由 \(N\) 个节点组成的树，每个节点有黑白两种颜色。定义一个节点 \(u\) 为好的当且仅当路径 \(1 \leftrightarrow u\) 上的节点均为黑色的，反之为坏的。初始情况下所有点均为白色。
定义一次操作为选取一个坏的节点并将其染黑，求将全部节点均染为黑色的期望操作次数，对 \(998244353\) 取模。
（\(2 \le N \le 2 \times 10^5\)）。
题解
发现所有节点均为黑色是所有节点均是好的的充要条件。所以我们可以将问题转化为求将所有节点变为好的的期望次数。
设 \(E(X_i)\) 代表直至第 \(i\) 期望变为好的，第 $i 个点期望被选中的次数，那么我们要求的所有节点的该值的和。
下面考虑如何计算该值，我们可以考虑先计算将第 \(i\) 个点变为好的的期望选择路径 \(1 \leftrightarrow u\) 上的节点的次数。可以发现该问题与如下问题等价：
有 \(n\) 种无限个的物品，每次随机等概率选择一种物品，求使得所有物品均被选择的期望次数。
可以考虑设当前选择了 \(k\) 种物品，那么下一次选择到新物品的概率为 \(\dfrac{n - k}{n}\)，那么选择到新物品的期望次数即为 \(\dfrac{n}{n - k}\)，那么总的期望次数即为
\[\sum\limits_{k = 0}^{n - 1}\dfrac{n}{n - k} = n\sum\limits_{i = 1}^{n}\dfrac{1}{i}
\]
发现在这个问题中不同种类的物品等价，那么我们可以得出
\[E(X_i) = \dfrac{\operatorname{depth}_u\sum\limits_{i = 1}^{\operatorname{depth}_u}\dfrac{1}{i}}{\operatorname{depth}_u} = \sum\limits_{i = 1}^{\operatorname{depth}_u}\dfrac{1}{i}
\]
\(\mathcal{O}(N)\) 求出即可。值得一提，由于本题规定每个节点的父亲节点编号小于该节点编号，所以无需显式建树。
Code
#include <bits/stdc++.h>
typedef long long valueType;
typedef std::vector<valueType> ValueVector;
constexpr valueType MOD = 998244353;
template<typename T1, typename T2, typename T3 = valueType>
void Inc(T1 &a, T2 b, const T3 &mod = MOD) {
a = a + b;
if (a >= mod)
a -= mod;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 sum(T1 a, T2 b, const T3 &mod = MOD) {
return a + b >= mod ? a + b - mod : a + b;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 mul(T1 a, T2 b, const T3 &mod = MOD) {
return (long long) a * b % mod;
}
template<typename T1, typename T2, typename T3 = valueType>
void Mul(T1 &a, T2 b, const T3 &mod = MOD) {
a = (long long) a * b % mod;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 pow(T1 a, T2 b, const T3 &mod = MOD) {
T1 result = 1;
while (b > 0) {
if (b & 1)
Mul(result, a, mod);
Mul(a, a, mod);
b = b >> 1;
}
return result;
}
class Inverse {
private:
valueType N;
ValueVector data;
public:
explicit Inverse(valueType n = 0) : N(n), data(n + 1) {
data[1] = 1;
for (valueType i = 2; i <= N; ++i)
data[i] = mul(MOD - MOD / i, data[MOD % i]);
}
valueType operator()(valueType n) const {
return data[n];
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
valueType N;
std::cin >> N;
Inverse const Inv(N);
ValueVector depth(N + 1);
depth[1] = 1;
ValueVector H(N + 1, 0);
for (valueType i = 1; i <= N; ++i)
H[i] = sum(H[i - 1], Inv(i));
valueType ans = H[1];
for (valueType i = 2; i <= N; ++i) {
valueType father;
std::cin >> father;
depth[i] = depth[father] + 1;
Inc(ans, H[depth[i]]);
}
std::cout << ans << std::endl;
return 0;
}