Yet Another Contest 8 P6 - Into the Woods

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 4.0s
Java 7.0s
Python 7.0s
Memory limit: 1G

Problem types

Andy is quite the fun guy. Bored with playing minecraft, he decides to venture out into the real world. Somehow, he wanders into an enchanted forest littered with various magical mushrooms.

After spending some time there, Andy observes that there are N distinct kinds of mushrooms, which he labels from type 0 to N-1. He also discovers that these mushrooms have a strange property: when the spores from mushrooms of type x and y come into contact, new mushrooms of type xy\pmod{N} are produced. Additionally, Andy notices that some of these mushrooms are able to use this method to produce mushrooms of type 1, starting with an unlimited number of spores of that mushroom. He calls any such type of mushroom an enigma mushroom.

As Andy journeys further into the woods, he finds a strange tree with N nodes labelled from 0 to N-1. The tree is rooted at node 0, and the parent of node i is u_i for all i > 0. He notices that a single type of mushroom grows on each node, and moreover, these types are pairwise distinct. That is, p_0, \ldots, p_{N-1} is a permutation of 0,\ldots,N-1, where p_i is the type of mushroom that grows on node i.

Andy considers of a subtree of this tree, S, to be enigmatic if the following conditions are met:

  • The only mushrooms in S are enigma mushrooms.
  • All mushrooms types that can be produced through spores by the mushrooms in S are already in S.
  • There exists a type of mushroom in S such that it is possible to grow every type of mushroom in S starting only with spores of this type.

Andy can't identify each mushroom individually, so he wants to know the minimum and maximum possible numbers of enigmatic subtrees over all possible p_0,\ldots,p_{N-1}, as well as the expected number of enigmatic subtrees, modulo 998244353, supposing that p_0,\ldots,p_{N-1} is a uniformly random permutation. He stubbornly refuses to leave until he gets his answers. Can you help out and get Andy out of the woods?

How to print an expected value modulo 998244353

It can be proven that the expected value to be found in this problem can be expressed uniquely as an irreducible fraction \frac{x}{y}, with y not divisible by 998244353. There exists a unique integer z between 0 and 998244352, inclusive, such that yz\equiv x\pmod{998244353}. Report this z.


2 \le N \le 10^6

0\le u_i < i for all i.

Subtask 1 [10%]

2 \le N \le 8

Subtask 2 [10%]

u_i = 0 for all i.

Subtask 3 [20%]

N is prime.

Subtask 4 [20%]

2 \le N \le 5\times 10^3

Subtask 5 [20%]

2 \le N \le 3\times10^5

Subtask 6 [20%]

No additional constraints.

Input Specification

The first line contains the integer N.

The second line contains N-1 integers u_1,\ldots, u_{N-1}.

Output Specification

On the first line, print the minimal number of enigmatic subtrees over all p_0,\ldots,p_{N-1}.

On the second line, print the maximal number of enigmatic subtrees over all p_0,\ldots,p_{N-1}.

On the third line, print the expected number of enigmatic subtrees over all p_0,\ldots,p_{N-1}, modulo 998244353.


You will receive 0\% of the points if you do not print three lines, where the first two lines contain a single integer between 0 and N, inclusive, and the third line contains a single integer between 0 and 998244352, inclusive.

You will receive 10\% of the points if your first line of output contains the correct answer.

You will receive 50\% of the points if your second line of output contains the correct answer.

You will receive 40\% of the points if your third line of output contains the correct answer.

The score for a subtask is the minimum score amongst any testcase in the subtask.

Sample Input 1

0 1 1 1

Sample Output 1


Explanation for Sample Output 1

A diagram of the tree with the nodes labelled is provided below.

First, note that it can be shown that mushrooms of type 1,2,3,4 are enigmatic, while mushrooms of type 0 are not.

Now consider the permutation p=[1, 0, 4, 2, 3]. In subtrees rooted at node 0 and 1, there exists a mushroom that is not enigmatic. In any other subtree, it can be shown that it can produce a mushroom type not in the subtree. Thus, there are no enigmatic subtrees.

Then, consider the permutation p=[0, 2, 1, 4, 3]. The subtree rooted at node 1 contains all types of enigmatic mushrooms. Moreover, it can be shown that any two mushrooms in the subtree produce another type of mushroom in the subtree. Finally, mushrooms of type 2 in the subtree can produce mushrooms of type 4, which then may be used to produce mushrooms of type 1 and 3. Thus, this subtree is an enigmatic subtree. The subtree rooted at 2 is also enigmatic. It can be shown that this is the maximum possible number of enigmatic subtrees.

It can be shown that over the 5!=120 different possible permutations of p_0,\ldots,p_{N-1}, 42 permutations yield 0 enigmatic subtrees, 60 permutations yield 1 enigmatic subtree, while the remaining 18 permutations yield 2 enigmatic subtrees. Thus, the desired expected value is \frac{42}{120}(0)+\frac{60}{120}(1)+\frac{18}{120}(2)=\frac{4}{5}\equiv399297742\pmod{998244353}.

Sample Input 2

0 0 1 1 2 2 3 3 4 4 5 5 6 6

Sample Output 2



There are no comments at the moment.