A15088 | K-Set Tree
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
You are given a tree $G$ with $n$ vertices and an integer $k$ . The vertices of the tree are numbered from $1$ to $n$ .
For a vertex $r$ and a subset $S$ of vertices of $G$ , such that $|S| = k$ , we define $f(r, S)$ as the size of the smallest rooted subtree containing all vertices in $S$ when the tree is rooted at $r$ . A set of vertices $T$ is called a rooted subtree, if all the vertices in $T$ are connected, and for each vertex in $T$ , all its descendants belong to $T$ .
You need to calculate the sum of $f(r, S)$ over all possible distinct combinations of vertices $r$ and subsets $S$ , where $|S| = k$ . Formally, compute the following: $$$$\sum_{r \in V} \sum_{S \subseteq V, |S| = k} f(r, S), $$ where $V$ is the set of vertices in $G$ .</p><p>Output the answer modulo $10^9 + 7$$$.
For a vertex $r$ and a subset $S$ of vertices of $G$ , such that $|S| = k$ , we define $f(r, S)$ as the size of the smallest rooted subtree containing all vertices in $S$ when the tree is rooted at $r$ . A set of vertices $T$ is called a rooted subtree, if all the vertices in $T$ are connected, and for each vertex in $T$ , all its descendants belong to $T$ .
You need to calculate the sum of $f(r, S)$ over all possible distinct combinations of vertices $r$ and subsets $S$ , where $|S| = k$ . Formally, compute the following: $$$$\sum_{r \in V} \sum_{S \subseteq V, |S| = k} f(r, S), $$ where $V$ is the set of vertices in $G$ .</p><p>Output the answer modulo $10^9 + 7$$$.
输入格式
The first line contains two integers $n$ and $k$ ( $3 \le n \le 2 \cdot 10^5$ , $1 \le k \le n$ ).
Each of the following $n - 1$ lines contains two integers $x$ and $y$ ( $1 \le x, y \le n$ ), denoting an edge between vertex $x$ and $y$ .
It is guaranteed that the given edges form a tree.
Each of the following $n - 1$ lines contains two integers $x$ and $y$ ( $1 \le x, y \le n$ ), denoting an edge between vertex $x$ and $y$ .
It is guaranteed that the given edges form a tree.
输出格式
Print the answer modulo $10^9 + 7$ .
输入输出样例
输入 #1
3 2 1 2 1 3
输出 #1
25
输入 #2
7 2 1 2 2 3 2 4 1 5 4 6 4 7
输出 #2
849
The tree in the second example is given below:
We have $21$ subsets of size $2$ in the given tree. Hence, $$$$S \in \left\{\{1, 2\}, \{1, 3\}, \{1, 4\}, \{1, 5\}, \{1, 6\}, \{1, 7\}, \{2, 3\}, \{2, 4\}, \{2, 5\}, \{2, 6\}, \{2, 7\}, \{3, 4\}, \{3, 5\}, \{3, 6\}, \{3, 7\}, \{4, 5\}, \{4, 6\}, \{4, 7\}, \{5, 6\}, \{5, 7\}, \{6, 7\} \right\}. $$ And since we have $7$ vertices, $1 \\le r \\le 7$ . We need to find the sum of $f(r, S)$ over all possible pairs of $r$ and $S$ . </p><p>Below we have listed the value of $f(r, S)$ for some combinations of $r$ and $S$ .</p><ul> <li> $r = 1$ , $S = \\{3, 7\\}$ . The value of $f(r, S)$ is $5$ and the corresponding subtree is $\\{2, 3, 4, 6, 7\\}$ . </li><li> $r = 1$ , $S = \\{5, 4\\}$ . The value of $f(r, S)$ is $7$ and the corresponding subtree is $\\{1, 2, 3, 4, 5, 6, 7\\}$ . </li><li> $r = 1$ , $S = \\{4, 6\\}$ . The value of $f(r, S)$ is $3$ and the corresponding subtree is $\\{4, 6, 7\\}$$$.
We have $21$ subsets of size $2$ in the given tree. Hence, $$$$S \in \left\{\{1, 2\}, \{1, 3\}, \{1, 4\}, \{1, 5\}, \{1, 6\}, \{1, 7\}, \{2, 3\}, \{2, 4\}, \{2, 5\}, \{2, 6\}, \{2, 7\}, \{3, 4\}, \{3, 5\}, \{3, 6\}, \{3, 7\}, \{4, 5\}, \{4, 6\}, \{4, 7\}, \{5, 6\}, \{5, 7\}, \{6, 7\} \right\}. $$ And since we have $7$ vertices, $1 \\le r \\le 7$ . We need to find the sum of $f(r, S)$ over all possible pairs of $r$ and $S$ . </p><p>Below we have listed the value of $f(r, S)$ for some combinations of $r$ and $S$ .</p><ul> <li> $r = 1$ , $S = \\{3, 7\\}$ . The value of $f(r, S)$ is $5$ and the corresponding subtree is $\\{2, 3, 4, 6, 7\\}$ . </li><li> $r = 1$ , $S = \\{5, 4\\}$ . The value of $f(r, S)$ is $7$ and the corresponding subtree is $\\{1, 2, 3, 4, 5, 6, 7\\}$ . </li><li> $r = 1$ , $S = \\{4, 6\\}$ . The value of $f(r, S)$ is $3$ and the corresponding subtree is $\\{4, 6, 7\\}$$$.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted