[ARC150D] Removing Gacha

由于期望的线性性，并且这个坏点的问题看上去不是很好处理，那么我们不妨想一想每个点会被涂黑多少次。
很显然一个点会被涂黑的次数可以移到链上考虑，并且深度大于这个点的点都不需要考虑。
我们可以看作在涂满之前随便选择，而不去考虑最长的涂黑前缀，为什么呢？

因为我们如果选择了一个最长涂黑前缀上的点，是对答案没有任何影响的，也就是说对于最后一个点来说选择任意选点无所谓，然后根据初中概率学，

随机选择一个点如果不合法就再选择一次等价于不考虑不合法的点进行选择。

那么对于一个深度为 \(d\) 的点，它被操作的期望步数就是随机涂黑链上全部 \(d\) 个点，最终他被涂黑的次数。这是经典问题。涂黑 \(i\) 个点之后，选择下一个白点的概率就是 \(\frac{n-i}{n}\) 期望步数就是 \(\frac{n}{n-i}\) 总期望步数就是 \(n\Sigma_{i=1}^{n}\frac{1}{i}=nH_n\)，每个点等价，那么每个点的操作步数都是 \(H_n\)（调和级数）。记 \(deepth[i]\) 为深度，本题的答案就是 \(\Sigma_xH_{deepth[x]}\)
代码如下

#include<bits/stdc++.h>
#define RG register
#define LL long long
#define U(x, y, z) for(RG int x = y; x <= z; ++x)
#define D(x, y, z) for(RG int x = y; x >= z; --x)
#define update(x, y) (x = x + y >= mod ? x + y - mod : x + y)
using namespace std;
void read(){}
template<typename _Tp, typename... _Tps>
void read(_Tp &x, _Tps &...Ar) {
	x = 0; char ch = getchar(); bool flg = 0;
	for (; !isdigit(ch); ch = getchar()) flg |= (ch == '-');
	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	if (flg) x = -x;
	read(Ar...);	
}
inline char Getchar(){ char ch; for (ch = getchar(); !isalpha(ch); ch = getchar()); return ch;}
template <typename T> inline void write(T n){ char ch[60]; bool f = 1; int cnt = 0; if (n < 0) f = 0, n = -n; do{ch[++cnt] = char(n % 10 + 48); n /= 10; }while(n); if (f == 0) putchar('-'); for (; cnt; cnt--) putchar(ch[cnt]);}
template <typename T> inline void writeln(T n){write(n); putchar('\n');}
template <typename T> inline void writesp(T n){write(n); putchar(' ');}
template <typename T> inline void chkmin(T &x, T y){x = x < y ? x : y;}
template <typename T> inline void chkmax(T &x, T y){x = x > y ? x : y;}
template <typename T> inline T Min(T x, T y){return x < y ? x : y;}
template <typename T> inline T Max(T x, T y){return x > y ? x : y;}
inline void readstr(string &s) { s = ""; static char c = getchar(); while (isspace(c)) c = getchar(); while (!isspace(c)) s = s + c, c = getchar();}
inline void FO(string s){freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout);}

const int N = 2e5 + 10, mod = 998244353;
LL inv[N], H[N];
int n, depth[N];

int main(){
	//FO("");
	read(n);
	inv[1] = 1;
	H[1] = 1;
	U(i, 2, n) {
		inv[i] = inv[mod % i] * (mod - mod / i) % mod;
		H[i] = H[i - 1];
		update(H[i], inv[i]);
	}
	// cerr << inv[10] * 10 % mod << "\n";
	depth[1] = 1;
	LL ans = 1;
	// cout << (1 + H[2] + H[2] + H[3]) % mod << '\n';
	U(i, 2, n) {
		int fa;
		read(fa);
		depth[i] = depth[fa] + 1;
		// cerr << depth[i] << "\n";
		update(ans, H[depth[i]]);
	}
	writeln(ans);
	return 0;
}