{"problem":{"name":"Removing Gacha","description":{"content":"We have a rooted tree with $N$ vertices numbered $1$ to $N$. Vertex $1$ is the root of the tree, and the parent of vertex $i\\ (2\\leq i)$ is vertex $p_i$. Each vertex has a color: black or white. Initi","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc150_d"},"statements":[{"statement_type":"Markdown","content":"We have a rooted tree with $N$ vertices numbered $1$ to $N$. Vertex $1$ is the root of the tree, and the parent of vertex $i\\ (2\\leq i)$ is vertex $p_i$.\nEach vertex has a color: black or white. Initially, all vertices are white.\nIn this rooted tree, vertex $i$ is said to be _good_ when all vertices on the simple path connecting vertices $1$ and $i$ (including vertices $1$ and $i$) are black, and _bad_ otherwise.\nUntil all vertices are black, let us repeat the following operation: choose one vertex from the bad vertices uniformly at random, and repaint the chosen vertex black.\nFind the expected value of the number of times we perform the operation, modulo $998244353$.\nThe definition of the expected value modulo $998244353$It can be proved that the sought expected value is always a rational number. Additionally, when that value is represented as an irreducible fraction $\\frac{P}{Q}$, it can also be proved that $Q \\not \\equiv 0 \\pmod{998244353}$. Therefore, there is a unique integer $R$ such that $R \\times Q \\equiv P \\pmod{998244353}$ and $0 \\leq R < 998244353$. Find this $R$.\n\n## Constraints\n\n*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq p_i < i$\n*   All values in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$p_2$ $p_3$ $\\dots$ $p_{N}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc150_d","tags":[],"sample_group":[["4\n1 1 3","831870300\n\nConsider a case where the first three operations have chosen vertices $1$, $2$, and $4$ in this order. Then, vertices $1$ and $2$ are good, but vertex $4$ is still bad since vertex $3$, an ancestor of vertex $4$, is white. Thus, the fourth operation will choose vertex $3$ or $4$ uniformly at random.\nThe expected value of the number of times we perform the operation is $\\displaystyle \\frac{35}{6}$."],["15\n1 2 1 1 4 5 3 3 5 10 3 6 3 13","515759610"]],"created_at":"2026-03-03 11:01:14"}}