Counting Similar Trees

A tree $T = (V, E)$ is a connected graph with no cycle, where $V = \{v_1, v_2, \ldots, v_n\}$ is its vertex set and $E = \{e_1, e_2, \ldots, e_{n-1}\}$ is its edge set. A labeled tree is a tree in which every vertex carries a distinct integer, that is, a one-to-one function $m_T : V \to \mathbb{Z}$ is given.

For $u, v \in V$, define $d_T(u, v) = m_T(u) - m_T(v)$. Two labeled trees $T_1 = (V_1, E_1)$ and $T_2 = (V_2, E_2)$ are similar when all three conditions hold.

1. $|V_1| = |V_2|$.
2. There is a bijection $f : V_1 \to V_2$ such that $(u, v) \in E_1$ if and only if $(f(u), f(v)) \in E_2$. That is, the two trees are isomorphic.
3. $d_{T_1}(u, v) = d_{T_2}(f(u), f(v))$ for every $(u, v) \in E_1$.

Figure 1: trees $T_1$ and $T_2$ are similar.

The two trees in Figure 1 are similar under this definition, and $f$ is the correspondence drawn in the figure. For instance, $d_{T_1}(v_1, v_2) = 1 - 9 = -8 = 9 - 17 = d_{T_2}(v_4, v_5)$, and $d_{T_1}(v_2, v_4) = 9 - 6 = 3 = 17 - 14 = d_{T_2}(v_5, v_1)$, and $d_{T_1}(v_2, v_3) = 9 - 7 = 2 = 17 - 15 = d_{T_2}(v_5, v_3)$.

You are given $d$ labeled trees. Similarity is an equivalence relation, so the trees split into groups of mutually similar trees. Find the size of every group.

The first line contains the number of labeled trees $d$ ($1 \le d \le 100$). Each tree is then given on two lines.

The first line of a tree lists all of its edges. One edge is written as the two numbers of its endpoints, so this line holds $2(n-1)$ integers for a tree with $n$ vertices. Vertices are numbered $1$ to $n$. The value of $n$ is not given separately, so recover it from the count of integers on this line. The second line of a tree gives the labels $m(v_1), m(v_2), \ldots, m(v_n)$ of the vertices $v_1, v_2, \ldots, v_n$ in that order.

$2 \le n \le 70000$ and $-100000 < m(v_i) < 100000$. The labels inside one tree are all distinct.

Print the size of every group on one line, from smallest to largest, separated by single spaces. The same size can appear more than once. A tree similar to no other tree forms a group of size $1$, and the printed numbers sum to $d$.