CF1707D Partial Virtual 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](https://en.wikipedia.org/wiki/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.

N/A

N/A

In the first test case, when $ k=1 $ , the only possible way is: 1. $ \{1,2,3,4\} \to \{1\} $ . When $ k=2 $ , there are $ 6 $ possible ways: 1. $ \{1,2,3,4\} \to \{1,2\} \to \{1\} $ ; 2. $ \{1,2,3,4\} \to \{1,2,3\} \to \{1\} $ ; 3. $ \{1,2,3,4\} \to \{1,2,4\} \to \{1\} $ ; 4. $ \{1,2,3,4\} \to \{1,3\} \to \{1\} $ ; 5. $ \{1,2,3,4\} \to \{1,3,4\} \to \{1\} $ ; 6. $ \{1,2,3,4\} \to \{1,4\} \to \{1\} $ . When $ k=3 $ , there are $ 6 $ possible ways: 1. $ \{1,2,3,4\} \to \{1,2,3\} \to \{1,2\} \to \{1\} $ ; 2. $ \{1,2,3,4\} \to \{1,2,3\} \to \{1,3\} \to \{1\} $ ; 3. $ \{1,2,3,4\} \to \{1,2,4\} \to \{1,2\} \to \{1\} $ ; 4. $ \{1,2,3,4\} \to \{1,2,4\} \to \{1,4\} \to \{1\} $ ; 5. $ \{1,2,3,4\} \to \{1,3,4\} \to \{1,3\} \to \{1\} $ ; 6. $ \{1,2,3,4\} \to \{1,3,4\} \to \{1,4\} \to \{1\} $ .