3427 . [模板題] Rooted Tree Isomorphism Classification

Submit out of contest
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Oyster

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

33.3% (2/6)

Tags

library-checker template

Description

Given a rooted tree with $N$ vertices. The root of tree is the vertex $0$ . A parent of the vertex $i$ is $p _ i$ . You will get $N$ rooted subtrees by choosing a root. Classify them by isomorphism of rooted trees.

Now print a number of distinct subtrees $K$ and an integer seqence $a _ 0 , a _ 1 , \ldots , a _ {N-1}$ that satisfy the following conditions.

  • $0 \leq a _ i \lt K$
  • $a _ i = a _ j$ if and only if the $2$ subtrees whose roots are $i$ and $j$ are isomorphic.

Input Format

$N$
$p _ 1$ $p _ 2$ $\ldots$ $p _ {N-1}$

Output Format

$K$
$a _ 0$ $a _ 1$ $\ldots$ $a _ {N-1}$

If there are multiple solutions, print any of them.

Sample Input 1

11
0 1 1 2 2 0 6 6 8 8

Sample Output 1

4
3 2 1 0 0 0 2 0 1 0 0

Sample Input 2

5
0 1 2 3

Sample Output 2

5
4 3 2 1 0

Hints

  • $1 \leq N \leq 5 \times 10^ {5}$
  • $0 \leq p _ i \lt i$

Problem Source

library checker: rooted_tree_isomorphism_classification

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 2097152 2097152
1 5000 2097152 2097152
2 5000 2097152 2097152
3 5000 2097152 2097152
4 5000 2097152 2097152
5 5000 2097152 2097152
6 5000 2097152 2097152
7 5000 2097152 2097152
8 5000 2097152 2097152
9 5000 2097152 2097152
10 5000 2097152 2097152
11 5000 2097152 2097152
12 5000 2097152 2097152
13 5000 2097152 2097152
14 5000 2097152 2097152
15 5000 2097152 2097152
16 5000 2097152 2097152
Submit out of contest
Back to Top