13386번 - Tree Count 다국어

A tree T = (V, E), where V = {v₁, v₂,..., v_n} is a set of vertices and E = {e₁, e₂,..., e_n-1} is a set of edges, is a connected graph with no cycle. A labeled tree T = (V, E) is a tree, where each of its vertices has an associated unique number. More precisely, there is a one-to-one function mT : V → {..., -2, -1, 0, 1, 2,...}.

Let d_T(u,v) = m_T(u) - m_T(v), where u, v ∈ V. Two labeled trees T₁ = (V₁, E₁) and T₂ = (V₂, E₂) are similar if and only if

1. |V_1| = |V₂|, and
2. There is a bijection such that (u,v) ∈ E₁ if and only if (f(u),f(v)) ∈ E₂. In other words, the trees are isomorphic.
3. Moreover, d_T1(u,v)=d_T2(f(u),f(v))for every(u,v) ∈ E₁.

Figure 1: Trees T₁ and T₂ are similar.

In Figure 1, trees T₁ and T₂ are similar according to the definition. The bijection is as drawn in the figure. Furthermore, it can be verified, for instance, that (v₁,v₂)= 1 - 9 = -8 = 9 - 17 = (v₄, v₅) and (v₂, v₄) = 9 - 6 = 3 = 17 - 14 = (v₅, v₁). Also, (v₂, v₃) = 9 - 7 = 2 = 17 - 15 = (v₅, v₃).

Given d labeled trees, your job is to count similar trees.

The first line of the input file contains the number of labeled trees d ≤ 100. 2 ≤ n ≤ 70,000. The following lines describe each tree and its labels. Each tree uses two lines to describe. The first line gives all edges of the tree. Tree nodes are numbered 1, 2, 3, ..., n. The second line gives the n labels of the tree in the order of vertices v₁, v₂, v₃, v₄,..., v_n. -100,000< m(v_i)< 100,000

There is only one line in the output file. This line contains the numbers of similar trees in the increasing order. Note that the sum of all numbers in this line is d.

Explanation of Sample Output: The first two 1s indicate that there are 2 trees that are not similar to any other trees. The next number (2) indicates that there are two trees that are similar to each other. Finally, the number 3 indicates that there are three trees that are similar to each other. Notice that the counts of similar trees are listed in increasing order and they sum to 7, which is the total of number given trees.