Binary Rooted Tree Isomorphism
In this task we are given a binary rooted tree T and we have to compute three integer values A, B, C.The value A is equal to binary logarithm of number of automorphisms of T.
The value B is equal to the maximum size of susbtree T1 of T such that there exists another subtree T2 of T, (T1 ≠ T2) isomorphic to T1.
The value C is the minimum depth of all subtrees isomorphic to T1.
Let us recall some necessary definitions. The concepts defined here are probably very well known to you, we provide the definitions just for the sake of completness.
-
A binary rooted tree T is a directed acyclic graph T = (V, E) for which holds:
1. Outdegree of each vertex of T is less or equal to 2.
2. If V is unempty then T contains exactly one root and indegree of each vertex other than root is equal to 1.
3. There is a mapping φ from E to set {L, R} such that for any two edges e1 = (a,b), e2 = (c,d), e1 ≠ e2 holds
(a = c) ⇒ φ(e1) ≠ φ(e2).
Given an edge (x,y) we call vertex y left or right child of x if φ((x,y)) = L or φ((x,y)) = R, respectively. - A directed path in the binary rooted tree is a sequence of edges in which the end node of any but the last edge is equal to the start node of the immediately following edge in the sequence. Number of edges in the sequence is the length of the path.
-
A subtree T1 of binary rooted tree T is a subgraph T1 of T which itself is a binary rooted tree and for which root r holds:
Whenever there is a directed path in T from r to some other vertex v ∈ V(T) then v is also a vertex of T1.
The left resp. right subtree of a vertex ∈ T is a subtree of T which root is the left resp. right child of x, if that child exists, otherwise it is empty. - The size of a tree T is defined as |V(T)|.
- The depth of a node v ∈ V(T) is the length of the (single) directed path from the root of T to v. Note that the depth of the root of a tree is 0. The depth of a subtree T1 of T is defined as the depth of the root of T1 in T.
-
An isomorphism between rooted binary trees T1 and T2 is a bijective mapping h: V(T1) → V(T2) with the property:
∀ a ∈ V(T1), ∀ b ∈ V(T1) : (a,b) ∈ E(T1) ⇒ (h(a), h(b)) ∈ E(T2). - An automorphism of binary rooted tree T is an isomorphism between T and T.
A vertex y ∈ V(T) is said to be to the left of a vertex x ∈ V(T) if the depth of x and y are equal and also there exists node z ∈ V(T) such that y is the element of the left subtree of z and x is the element of the right subtree of z. Left order of a node x ∈ V(T) is a number of all vertices y ∈ V(T) which are to the left of x. We denote left order of x by LO(x).
Note: It can beasily proven (e.g by induction on tree height) that the number of automorphisms on a binary rooted tree is always a power of two. The number may be quite big even on relatively small trees, for example on a binary rooted tree with 127 vertices there may exist 170141183460469231731687303715884105728 different automorphisms. Therefore we are interested only in logarithms of those numbers.
Input
First line contains two positive integers D and M. D is the maximum possible depth of any node in the tree. M represents the set SETM = {0, 1, 2, ..., M−1}. Set SETM is divided into four mutually disjoint subsets M0, M1, M2, M3, which we use to specify children of each node. It holds M0 ∪ M1 ∪ M2 ∪ M3 = SETM. Note that some of sets M0, M1, M2, M3 (maximum three of them) might be empty.Next three lines of input specify sets M1, M2, M3 in this order, each set on a single line. Each set is represented by a sequence of its elements which may appear in any order. The sequence of elements is preceeded by a single integer specifying the cardinality of the set. All values on a line are separated by one or more spaces.
Set M0 is not given explicitly as it can be easily determined using the equality M0 = SETM − (M1 ∪ M2 ∪ M3).
The input binary rooted tree T is specified as follows:
First, we define generating function f on each node x ∈ V(T) as
f(x) = ((LO(x)2+depth(x)) mod M.
For each vertex v ∈ V(T) holds:
If depth(x) = D then x is a leaf.
If depth(x) < D then
if f(x) ∈ M0 then x is a leaf,
if f(x) ∈ M1 then x has only left child,
if f(x) ∈ M2 then x has only right child,
if f(x) ∈ M3 then x has both left and right children.
T is unempty and its size does not exceed 104. Values of D and M do not exceed 103. You may assume that the problem input data do not produce ambiguity regarding the value of C (which would otherwise sometimes depend on the choice of subtree T1 during calculation of value B).
Output
The output contains one line with numbers A, B, C, specified above. The values are separated by one space. When there are no two different subtrees of T isomorphic to one another then the values of B and C are 0.Example 1
Input:5 5 0 0 3 0 1 2Output:
4 5 1The input tree is presented here for readers convenience, rotated 90° to the left. Two subtrees at which B is attained are rooted at the vertices at lines 7 and 3, C is attained at line 3.
18 +-[xx]
17 +-[xx]
16 | +-[xx]
15 +-[xx]
14 | | +-[xx]
13 | | +-[xx]
12 | | | +-[xx]
11 | +-[xx]
10 | | +-[xx]
9 | | +-[xx]
8 | | | +-[xx]
7 | +-[xx]
6 | +-[xx]
5 [xx]
4 | +-[xx]
3 +-[xx]
2 | +-[xx]
1 +-[xx]
0 +-[xx]
Example 2
Input:4 10 2 1 3 1 2 6 0 4 5 6 7 8Output:
1 1 4The input tree is presented here for readers convenience, rotated 90° to the left. Three subtrees at which B is attained are rooted at the vertices at lines 8, 6, 1, C is attained at all of them.
9 +-[xx]
8 | | +-[xx]
7 | +-[xx]
6 | +-[xx]
5 +-[xx]
4 [xx]
3 +-[xx]
2 | +-[xx]
1 | | +-[xx]
0 +-[xx]
Example 3
Input:4 4 1 3 1 2 2 0 1Output:
1 3 2The input tree is presented here for readers convenience, rotated 90° to the left. Two subtrees at which B is attained are rooted at the vertices at lines 0 and 10, C is attained at both of them.
12 +-[xx]
11 | +-[xx]
10 +-[xx]
9 +-[xx]
8 [xx]
7 | +-[xx]
6 | | | +-[xx]
5 | | +-[xx]
4 | | +-[xx]
3 +-[xx]
2 | +-[xx]
1 | | +-[xx]
0 +-[xx]
Example 4
Input:14 5 0 0 3 0 1 2Output:
22 7 7The input tree is presented here for readers convenience, rotated 90° to the left. Two subtrees at which B is attained are rooted at the vertices at lines 61 and 35, C is attained at line 61.
114 +-[xx]
113 +-[xx]
112 | +-[xx]
111 +-[xx]
110 | | +-[xx]
109 | | +-[xx]
108 | | | +-[xx]
107 | +-[xx]
106 | | +-[xx]
105 | | +-[xx]
104 | | | | +-[xx]
103 | | | +-[xx]
102 | | | | +-[xx]
101 | | | | +-[xx]
100 | | | | | | +-[xx]
99 | | | | | +-[xx]
98 | | | | | +-[xx]
97 | | | | +-[xx]
96 | | | | | +-[xx]
95 | | | | +-[xx]
94 | | | | | | +-[xx]
93 | | | | | | +-[xx]
92 | | | | | | | +-[xx]
91 | | | | | | +-[xx]
90 | | | | | | | +-[xx]
89 | | | | | +-[xx]
88 | | | | | | +-[xx]
87 | | | | | +-[xx]
86 | | | | | +-[xx]
85 | | | +-[xx]
84 | | | | +-[xx]
83 | | | | +-[xx]
82 | | | | | | +-[xx]
81 | | | | | | +-[xx]
80 | | | | | | | +-[xx]
79 | | | | | +-[xx]
78 | | | | | | +-[xx]
77 | | | | | +-[xx]
76 | | | | | +-[xx]
75 | | | +-[xx]
74 | | | | +-[xx]
73 | | | +-[xx]
72 | | | | +-[xx]
71 | | | +-[xx]
70 | | | +-[xx]
69 | | +-[xx]
68 | | | +-[xx]
67 | | +-[xx]
66 | | | | +-[xx]
65 | | | | +-[xx]
64 | | | | | | +-[xx]
63 | | | | | +-[xx]
62 | | | | | +-[xx]
61 | | | | +-[xx]
60 | | | | | +-[xx]
59 | | | +-[xx]
58 | | | +-[xx]
57 | | +-[xx]
56 | | | | +-[xx]
55 | | | | +-[xx]
54 | | | | | +-[xx]
53 | | | | +-[xx]
52 | | | | | | +-[xx]
51 | | | | | | +-[xx]
50 | | | | | | | +-[xx]
49 | | | | | +-[xx]
48 | | | | | | +-[xx]
47 | | | | | | +-[xx]
46 | | | | | | | | +-[xx]
45 | | | | | | | +-[xx]
44 | | | | | | | +-[xx]
43 | | | | | | +-[xx]
42 | | | | | | | +-[xx]
41 | | | | | | +-[xx]
40 | | | | | | | | +-[xx]
39 | | | | | | | | +-[xx]
38 | | | | | | | | | +-[xx]
37 | | | | | | | | +-[xx]
36 | | | | | | | | | +-[xx]
35 | | | | | | | +-[xx]
34 | | | | | | | +-[xx]
33 | | | | | | +-[xx]
32 | | | | | | | | +-[xx]
31 | | | | | | | | +-[xx]
30 | | | | | | | | | +-[xx]
29 | | | | | | | | +-[xx]
28 | | | | | | | | | | +-[xx]
27 | | | | | | | | | | +-[xx]
26 | | | | | | | | | | | +-[xx]
25 | | | | | | | | | +-[xx]
24 | | | | | | | | | | +-[xx]
23 | | | | | | | | | +-[xx]
22 | | | | | | | | | +-[xx]
21 | | | | | | | +-[xx]
20 | | | | | | | | +-[xx]
19 | | | | | | | +-[xx]
18 | | | | | | | | +-[xx]
17 | | | | | | | +-[xx]
16 | | | | | | | +-[xx]
15 | | | | | +-[xx]
14 | | | | | +-[xx]
13 | | | +-[xx]
12 | | | | +-[xx]
11 | | | +-[xx]
10 | | | | +-[xx]
9 | | | +-[xx]
8 | | | +-[xx]
7 | +-[xx]
6 | +-[xx]
5 [xx]
4 | +-[xx]
3 +-[xx]
2 | +-[xx]
1 +-[xx]
0 +-[xx]
Example 5
Input:30 6 1 4 1 0 3 1 2 3Output:
3614 220 19
The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout a stderr is returned on the evaluation feedback page.