309617: CF1707D. Partial Virtual Trees
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Partial Virtual Trees
题意翻译
给定 $n$ 个点的树以及质数 $p$，对每个 $k=1,2,\cdots,n-1$ 计算满足下述条件的点集序列 $\{S_i\}_{i=0}^k$ 数量 $\bmod\ p$： - $\{1\}=S_k\subsetneq S_{k-1}\subsetneq\cdots\subsetneq S_0=\{1,2,\cdots,n\}$； - 对每个 $S_i$ 以及 $u,v\in S_i$，都有 $\text{LCA}(u,v)\in S_i$。 其中 $\text{LCA}(u,v)$ 表示以 $1$ 为根时 $u$ 与 $v$ 的最近公共祖先。题目描述
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.输入输出格式
输入格式
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 $ .
输入输出样例
输入样例 #1
4 998244353
1 2
2 3
1 4输出样例 #1
1 6 6输入样例 #2
7 100000007
1 2
1 3
2 4
2 5
3 6
3 7输出样例 #2
1 47 340 854 880 320输入样例 #3
8 1000000007
1 2
2 3
3 4
4 5
5 6
6 7
7 8输出样例 #3
1 126 1806 8400 16800 15120 5040说明
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\} $ .Input
题意翻译
给定 $n$ 个点的树以及质数 $p$，对每个 $k=1,2,\cdots,n-1$ 计算满足下述条件的点集序列 $\{S_i\}_{i=0}^k$ 数量 $\bmod\ p$： - $\{1\}=S_k\subsetneq S_{k-1}\subsetneq\cdots\subsetneq S_0=\{1,2,\cdots,n\}$； - 对每个 $S_i$ 以及 $u,v\in S_i$，都有 $\text{LCA}(u,v)\in S_i$。 其中 $\text{LCA}(u,v)$ 表示以 $1$ 为根时 $u$ 与 $v$ 的最近公共祖先。Output
**题意翻译：**
给定一个有 $ n $ 个点的树和一个质数 $ p $，对于每个 $ k = 1,2,\ldots,n-1 $，计算满足以下条件的点集序列 $\{S_i\}_{i=0}^k$ 的数量 $\bmod\ p$：
- $\{1\} = S_k \subsetneq S_{k-1} \subsetneq \cdots \subsetneq S_0 = \{1,2,\ldots,n\}$；
- 对于每个 $ S_i $ 以及 $ u,v \in S_i $，都有 $\text{LCA}(u,v) \in S_i$。
其中 $\text{LCA}(u,v)$ 表示以 $ 1 $ 为根时 $ u $ 与 $ v $ 的最近公共祖先。
**题目描述：**
Kawashiro Nitori 是一个热爱竞技编程的女孩。有一天她找到了一个由 $ n $ 个顶点组成的树，根节点是顶点 $ 1 $。作为一个高级问题设定者，她迅速想到了一个问题。
Kawashiro Nitori 有一个顶点集合 $ U = \{1,2,\ldots,n\} $。她将用这棵树和集合进行游戏。在每次操作中，她会选择一个顶点集合 $ T $，其中 $ T $ 是 $ U $ 的一个部分虚拟树，并将 $ U $ 变为 $ T $。
一个顶点集合 $ S_1 $ 是另一个顶点集合 $ S_2 $ 的部分虚拟树，如果 $ S_1 $ 是 $ S_2 $ 的子集，$ S_1 \neq S_2 $，并且对于 $ S_1 $ 中的任意两个顶点 $ i $ 和 $ j $，$ \operatorname{LCA}(i,j) $ 都在 $ S_1 $ 中，其中 $ \operatorname{LCA}(x,y) $ 表示树上顶点 $ x $ 和 $ y $ 的最低公共祖先。注意，一个顶点集合可以有多个不同的部分虚拟树。
Kawashiro Nitori 想要知道，对于每个可能的 $ k $，如果她恰好执行 $ k $ 次操作，最终有多少种方式可以让 $ U = \{1\} $？如果有整数 $ z $（$ 1 \le z \le k $），使得在 $ z $ 次操作后集合 $ U $ 不同，则认为两种方式是不同的。
由于答案可能非常大，你需要找到它模 $ p $ 的值。保证 $ p $ 是一个质数。
**输入输出格式：**
**输入格式：**
第一行包含两个整数 $ n $ 和 $ p $（$ 2 \le n \le 2000 $，$ 10^8 + 7 \le p \le 10^9+9 $）。保证 $ p $ 是一个质数。
接下来 $ n-1 $ 行，每行包含两个整数 $ u_i $ 和 $ v_i $（$ 1 \leq u_i, v_i \leq n $），表示 $ u_i $ 和 $ v_i $ 之间的边。
保证给定的边构成一棵树。
**输出格式：**
仅一行，包含 $ n-1 $ 个整数——对于 $ k=1,2,\ldots,n-1 $ 的答案模 $ p $。
**输入输出样例：**
**输入样例 #1：**
```
4 998244353
1 2
2 3
1 4
```
**输出样例 #1：**
```
1 6 6
```
**输入样例 #2：**
```
7 100000007
1 2
1 3
2 4
2 5
3 6
3 7
```
**输出样例 #2：**
```
1 47 340 854 880 320
```
**输入样例 #3：**
```
8 1000000007
1 2
2 3
3 4
4 5
5 6
6 7
7 8
```
**输出样例 #3：**
```
1 126 1806 8400 16800 15120 5040
```**题意翻译：** 给定一个有 $ n $ 个点的树和一个质数 $ p $，对于每个 $ k = 1,2,\ldots,n-1 $，计算满足以下条件的点集序列 $\{S_i\}_{i=0}^k$ 的数量 $\bmod\ p$： - $\{1\} = S_k \subsetneq S_{k-1} \subsetneq \cdots \subsetneq S_0 = \{1,2,\ldots,n\}$； - 对于每个 $ S_i $ 以及 $ u,v \in S_i $，都有 $\text{LCA}(u,v) \in S_i$。 其中 $\text{LCA}(u,v)$ 表示以 $ 1 $ 为根时 $ u $ 与 $ v $ 的最近公共祖先。 **题目描述：** Kawashiro Nitori 是一个热爱竞技编程的女孩。有一天她找到了一个由 $ n $ 个顶点组成的树，根节点是顶点 $ 1 $。作为一个高级问题设定者，她迅速想到了一个问题。 Kawashiro Nitori 有一个顶点集合 $ U = \{1,2,\ldots,n\} $。她将用这棵树和集合进行游戏。在每次操作中，她会选择一个顶点集合 $ T $，其中 $ T $ 是 $ U $ 的一个部分虚拟树，并将 $ U $ 变为 $ T $。 一个顶点集合 $ S_1 $ 是另一个顶点集合 $ S_2 $ 的部分虚拟树，如果 $ S_1 $ 是 $ S_2 $ 的子集，$ S_1 \neq S_2 $，并且对于 $ S_1 $ 中的任意两个顶点 $ i $ 和 $ j $，$ \operatorname{LCA}(i,j) $ 都在 $ S_1 $ 中，其中 $ \operatorname{LCA}(x,y) $ 表示树上顶点 $ x $ 和 $ y $ 的最低公共祖先。注意，一个顶点集合可以有多个不同的部分虚拟树。 Kawashiro Nitori 想要知道，对于每个可能的 $ k $，如果她恰好执行 $ k $ 次操作，最终有多少种方式可以让 $ U = \{1\} $？如果有整数 $ z $（$ 1 \le z \le k $），使得在 $ z $ 次操作后集合 $ U $ 不同，则认为两种方式是不同的。 由于答案可能非常大，你需要找到它模 $ p $ 的值。保证 $ p $ 是一个质数。 **输入输出格式：** **输入格式：** 第一行包含两个整数 $ n $ 和 $ p $（$ 2 \le n \le 2000 $，$ 10^8 + 7 \le p \le 10^9+9 $）。保证 $ p $ 是一个质数。 接下来 $ n-1 $ 行，每行包含两个整数 $ u_i $ 和 $ v_i $（$ 1 \leq u_i, v_i \leq n $），表示 $ u_i $ 和 $ v_i $ 之间的边。 保证给定的边构成一棵树。 **输出格式：** 仅一行，包含 $ n-1 $ 个整数——对于 $ k=1,2,\ldots,n-1 $ 的答案模 $ p $。 **输入输出样例：** **输入样例 #1：** ``` 4 998244353 1 2 2 3 1 4 ``` **输出样例 #1：** ``` 1 6 6 ``` **输入样例 #2：** ``` 7 100000007 1 2 1 3 2 4 2 5 3 6 3 7 ``` **输出样例 #2：** ``` 1 47 340 854 880 320 ``` **输入样例 #3：** ``` 8 1000000007 1 2 2 3 3 4 4 5 5 6 6 7 7 8 ``` **输出样例 #3：** ``` 1 126 1806 8400 16800 15120 5040 ```
给定一个有 $ n $ 个点的树和一个质数 $ p $，对于每个 $ k = 1,2,\ldots,n-1 $，计算满足以下条件的点集序列 $\{S_i\}_{i=0}^k$ 的数量 $\bmod\ p$：
- $\{1\} = S_k \subsetneq S_{k-1} \subsetneq \cdots \subsetneq S_0 = \{1,2,\ldots,n\}$；
- 对于每个 $ S_i $ 以及 $ u,v \in S_i $，都有 $\text{LCA}(u,v) \in S_i$。
其中 $\text{LCA}(u,v)$ 表示以 $ 1 $ 为根时 $ u $ 与 $ v $ 的最近公共祖先。
**题目描述：**
Kawashiro Nitori 是一个热爱竞技编程的女孩。有一天她找到了一个由 $ n $ 个顶点组成的树，根节点是顶点 $ 1 $。作为一个高级问题设定者，她迅速想到了一个问题。
Kawashiro Nitori 有一个顶点集合 $ U = \{1,2,\ldots,n\} $。她将用这棵树和集合进行游戏。在每次操作中，她会选择一个顶点集合 $ T $，其中 $ T $ 是 $ U $ 的一个部分虚拟树，并将 $ U $ 变为 $ T $。
一个顶点集合 $ S_1 $ 是另一个顶点集合 $ S_2 $ 的部分虚拟树，如果 $ S_1 $ 是 $ S_2 $ 的子集，$ S_1 \neq S_2 $，并且对于 $ S_1 $ 中的任意两个顶点 $ i $ 和 $ j $，$ \operatorname{LCA}(i,j) $ 都在 $ S_1 $ 中，其中 $ \operatorname{LCA}(x,y) $ 表示树上顶点 $ x $ 和 $ y $ 的最低公共祖先。注意，一个顶点集合可以有多个不同的部分虚拟树。
Kawashiro Nitori 想要知道，对于每个可能的 $ k $，如果她恰好执行 $ k $ 次操作，最终有多少种方式可以让 $ U = \{1\} $？如果有整数 $ z $（$ 1 \le z \le k $），使得在 $ z $ 次操作后集合 $ U $ 不同，则认为两种方式是不同的。
由于答案可能非常大，你需要找到它模 $ p $ 的值。保证 $ p $ 是一个质数。
**输入输出格式：**
**输入格式：**
第一行包含两个整数 $ n $ 和 $ p $（$ 2 \le n \le 2000 $，$ 10^8 + 7 \le p \le 10^9+9 $）。保证 $ p $ 是一个质数。
接下来 $ n-1 $ 行，每行包含两个整数 $ u_i $ 和 $ v_i $（$ 1 \leq u_i, v_i \leq n $），表示 $ u_i $ 和 $ v_i $ 之间的边。
保证给定的边构成一棵树。
**输出格式：**
仅一行，包含 $ n-1 $ 个整数——对于 $ k=1,2,\ldots,n-1 $ 的答案模 $ p $。
**输入输出样例：**
**输入样例 #1：**
```
4 998244353
1 2
2 3
1 4
```
**输出样例 #1：**
```
1 6 6
```
**输入样例 #2：**
```
7 100000007
1 2
1 3
2 4
2 5
3 6
3 7
```
**输出样例 #2：**
```
1 47 340 854 880 320
```
**输入样例 #3：**
```
8 1000000007
1 2
2 3
3 4
4 5
5 6
6 7
7 8
```
**输出样例 #3：**
```
1 126 1806 8400 16800 15120 5040
```**题意翻译：** 给定一个有 $ n $ 个点的树和一个质数 $ p $，对于每个 $ k = 1,2,\ldots,n-1 $，计算满足以下条件的点集序列 $\{S_i\}_{i=0}^k$ 的数量 $\bmod\ p$： - $\{1\} = S_k \subsetneq S_{k-1} \subsetneq \cdots \subsetneq S_0 = \{1,2,\ldots,n\}$； - 对于每个 $ S_i $ 以及 $ u,v \in S_i $，都有 $\text{LCA}(u,v) \in S_i$。 其中 $\text{LCA}(u,v)$ 表示以 $ 1 $ 为根时 $ u $ 与 $ v $ 的最近公共祖先。 **题目描述：** Kawashiro Nitori 是一个热爱竞技编程的女孩。有一天她找到了一个由 $ n $ 个顶点组成的树，根节点是顶点 $ 1 $。作为一个高级问题设定者，她迅速想到了一个问题。 Kawashiro Nitori 有一个顶点集合 $ U = \{1,2,\ldots,n\} $。她将用这棵树和集合进行游戏。在每次操作中，她会选择一个顶点集合 $ T $，其中 $ T $ 是 $ U $ 的一个部分虚拟树，并将 $ U $ 变为 $ T $。 一个顶点集合 $ S_1 $ 是另一个顶点集合 $ S_2 $ 的部分虚拟树，如果 $ S_1 $ 是 $ S_2 $ 的子集，$ S_1 \neq S_2 $，并且对于 $ S_1 $ 中的任意两个顶点 $ i $ 和 $ j $，$ \operatorname{LCA}(i,j) $ 都在 $ S_1 $ 中，其中 $ \operatorname{LCA}(x,y) $ 表示树上顶点 $ x $ 和 $ y $ 的最低公共祖先。注意，一个顶点集合可以有多个不同的部分虚拟树。 Kawashiro Nitori 想要知道，对于每个可能的 $ k $，如果她恰好执行 $ k $ 次操作，最终有多少种方式可以让 $ U = \{1\} $？如果有整数 $ z $（$ 1 \le z \le k $），使得在 $ z $ 次操作后集合 $ U $ 不同，则认为两种方式是不同的。 由于答案可能非常大，你需要找到它模 $ p $ 的值。保证 $ p $ 是一个质数。 **输入输出格式：** **输入格式：** 第一行包含两个整数 $ n $ 和 $ p $（$ 2 \le n \le 2000 $，$ 10^8 + 7 \le p \le 10^9+9 $）。保证 $ p $ 是一个质数。 接下来 $ n-1 $ 行，每行包含两个整数 $ u_i $ 和 $ v_i $（$ 1 \leq u_i, v_i \leq n $），表示 $ u_i $ 和 $ v_i $ 之间的边。 保证给定的边构成一棵树。 **输出格式：** 仅一行，包含 $ n-1 $ 个整数——对于 $ k=1,2,\ldots,n-1 $ 的答案模 $ p $。 **输入输出样例：** **输入样例 #1：** ``` 4 998244353 1 2 2 3 1 4 ``` **输出样例 #1：** ``` 1 6 6 ``` **输入样例 #2：** ``` 7 100000007 1 2 1 3 2 4 2 5 3 6 3 7 ``` **输出样例 #2：** ``` 1 47 340 854 880 320 ``` **输入样例 #3：** ``` 8 1000000007 1 2 2 3 3 4 4 5 5 6 6 7 7 8 ``` **输出样例 #3：** ``` 1 126 1806 8400 16800 15120 5040 ```