D. Partial Virtual Trees
combinatorics; dfs and similar; dp; math; trees
Kawashiro Nitori is a girl who loves competitive programming. One day she found a rooted tree consisting of \(n\) vertices. The root is vertex \(1\). As an advanced problem setter, she quickly thought of a problem.Kawashiro Nitori has a vertex set \(U=\{1,2,\ldots,n\}\). She's going to play a game with the tree and the set. In each operation, she will choose a vertex set \(T\), where \(T\) is a partial virtual tree of \(U\), and change \(U\) into \(T\).A vertex set \(S_1\) is a partial virtual tree of a vertex set \(S_2\), if \(S_1\) is a subset of \(S_2\), \(S_1 \neq S_2\), and for all pairs of vertices \(i\) and \(j\) in \(S_1\), \(\operatorname{LCA}(i,j)\) is in \(S_1\), where \(\operatorname{LCA}(x,y)\) denotes the lowest common ancestor of vertices \(x\) and \(y\) on the tree. Note that a vertex set can have many different partial virtual trees.Kawashiro Nitori wants to know for each possible \(k\), if she performs the operation exactly \(k\) times, in how many ways she can make \(U=\{1\}\) in the end? Two ways are considered different if there exists an integer \(z\) (\(1 \le z \le k\)) such that after \(z\) operations the sets \(U\) are different.Since the answer could be very large, you need to find it modulo \(p\). It's guaranteed that \(p\) is a prime number.
The first line contains two integers \(n\) and \(p\) (\(2 \le n \le 2000\), \(10^8 + 7 \le p \le 10^9+9\)). It's guaranteed that \(p\) is a prime number.Each of the next \(n-1\) lines contains two integers \(u_i\), \(v_i\) (\(1 \leq u_i, v_i \leq n\)), representing an edge between \(u_i\) and \(v_i\).It is guaranteed that the given edges form a tree.
The only line contains \(n-1\) integers — the answer modulo \(p\) for \(k=1,2,\ldots,n-1\).
In the first test case, when \(k=1\), the only possible way is: \(\{1,2,3,4\} \to \{1\}\). When \(k=2\), there are \(6\) possible ways: \(\{1,2,3,4\} \to \{1,2\} \to \{1\}\); \(\{1,2,3,4\} \to \{1,2,3\} \to \{1\}\); \(\{1,2,3,4\} \to \{1,2,4\} \to \{1\}\); \(\{1,2,3,4\} \to \{1,3\} \to \{1\}\); \(\{1,2,3,4\} \to \{1,3,4\} \to \{1\}\); \(\{1,2,3,4\} \to \{1,4\} \to \{1\}\). When \(k=3\), there are \(6\) possible ways: \(\{1,2,3,4\} \to \{1,2,3\} \to \{1,2\} \to \{1\}\); \(\{1,2,3,4\} \to \{1,2,3\} \to \{1,3\} \to \{1\}\); \(\{1,2,3,4\} \to \{1,2,4\} \to \{1,2\} \to \{1\}\); \(\{1,2,3,4\} \to \{1,2,4\} \to \{1,4\} \to \{1\}\); \(\{1,2,3,4\} \to \{1,3,4\} \to \{1,3\} \to \{1\}\); \(\{1,2,3,4\} \to \{1,3,4\} \to \{1,4\} \to \{1\}\).