A7633. [ABC133E] Virus Tree 2
编程题
普及+/提高
知识点
题目描述
给定一棵有 $N$ 个顶点、$N-1$ 条边的树。顶点编号为 $1,2,\ldots,N$，第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。
你有 $K$ 种颜色的颜料。你需要给树的每个顶点选择一种颜色进行涂色，要求满足以下条件：
- 对于任意两个距离不超过 $2$ 的不同顶点 $x,y$，顶点 $x$ 和顶点 $y$ 的颜色必须不同。
请计算有多少种不同的涂色方法。将结果对 $1,000,000,007$ 取模后输出。
**关于树**
树是一种特殊的图。详情请参考：[Wikipedia「木 (数学)」](https://ja.wikipedia.org/wiki/%E6%9C%A8_(%E6%95%B0%E5%AD%A6))。
**关于距离**
两个顶点 $x,y$ 之间的距离是指从 $x$ 到 $y$ 需要经过的最少边数。
你有 $K$ 种颜色的颜料。你需要给树的每个顶点选择一种颜色进行涂色，要求满足以下条件：
- 对于任意两个距离不超过 $2$ 的不同顶点 $x,y$，顶点 $x$ 和顶点 $y$ 的颜色必须不同。
请计算有多少种不同的涂色方法。将结果对 $1,000,000,007$ 取模后输出。
**关于树**
树是一种特殊的图。详情请参考：[Wikipedia「木 (数学)」](https://ja.wikipedia.org/wiki/%E6%9C%A8_(%E6%95%B0%E5%AD%A6))。
**关于距离**
两个顶点 $x,y$ 之间的距离是指从 $x$ 到 $y$ 需要经过的最少边数。
输入格式
输入通过标准输入按以下格式给出：
> $N$ $K$
> $a_1$ $b_1$
> $a_2$ $b_2$
> $\cdots$
> $a_{N-1}$ $b_{N-1}$
> $N$ $K$
> $a_1$ $b_1$
> $a_2$ $b_2$
> $\cdots$
> $a_{N-1}$ $b_{N-1}$
输出格式
输出树的所有合法涂色方法数，对 $1,000,000,007$ 取模后的结果。
输入输出样例
输入 #1
4 3 1 2 2 3 3 4
输出 #1
6
输入 #2
5 4 1 2 1 3 1 4 4 5
输出 #2
48
输入 #3
16 22 12 1 3 1 4 16 7 12 6 2 2 15 5 16 14 16 10 11 3 10 3 13 8 6 16 8 9 12 4 3
输出 #3
271414432
说明/提示
### 限制条件
- $1 \leq N,K \leq 10^5$
- $1 \leq a_i,b_i \leq N$
- 输入保证给定的图是一棵树。
### 样例解释 1
共有 $6$ 种不同的涂色方法。
- $1 \leq N,K \leq 10^5$
- $1 \leq a_i,b_i \leq N$
- 输入保证给定的图是一棵树。
### 样例解释 1
共有 $6$ 种不同的涂色方法。