P4516 [JSOI2018] Infiltration Operation

The aliens are attacking Earth yet again, and the alien mothership is already en route to Earth. This time, `JYY` has contacted the Golden Fleet and plans to unite all `JSOIer` to resist the alien invasion. Before the Golden Fleet takes position, `JYY` intends to first learn the aliens' plan. Now, an agent carrying listening devices has secretly infiltrated the alien mothership to eavesdrop on their communications. The alien mothership can be regarded as an **undirected tree** with $n$ nodes and $n-1$ edges. The nodes on the tree are numbered $1,2,\cdots,n$. The agent employed by `JYY` is equipped with a stealth module, allowing free movement within the mothership and the ability to install listening devices on nodes without being detected. If a listening device is installed at node $u$, then `JYY` can monitor the communications of all nodes **directly adjacent** to $u$. In other words, if a device is placed at node $u$, then for every edge $(u,v)$ in the tree, node $v$ will be monitored. Note in particular that a device placed at node $u$ does not monitor the communications of $u$ itself; this is a tactic designed by `JYY` to avoid detection by the aliens. The agent carries exactly $k$ listening devices. `JYY` wants to know how many different ways there are to place the devices so that the communications of **all nodes** on the mothership are monitored. To avoid waste, at most one device may be installed on each node, and all devices must be used.

The first line of input contains two integers $n,k$, representing the number of nodes $n$ of the mothership and the number of listening devices $k$. The next $n-1$ lines each contain two integers $u,v$ $(1\le u,v\le n)$, representing an edge in the tree.

Output a single line containing the number of valid configurations. Since the answer may be large, you only need to output the remainder $\text{mod 1,000,000,007}$.

Explanation for Sample 1 The sample is a chain $1-2-3-4-5$. First, nodes $2$ and $4$ must have devices; otherwise $1$ and $5$ cannot be monitored (a device does not monitor the node it sits on). The remaining device must be placed on node $3$ to monitor both $2$ and $4$. Therefore, placing devices on nodes $2,3,4$ is the only valid configuration. Constraints - For $10\%$ of the testdata, $1 \le n \le 20$. - For another $10\%$ of the testdata, $1 \le n \le 100$. - For another $10\%$ of the testdata, $1 \le k \le 10$. - For another $10\%$ of the testdata, the input tree is a chain. - For all testdata, $1\le n\le 10^5$, $1\le k\le \min\{n,100\}$. Translated by ChatGPT 5