小風是一個愛塗色的人,他看到甚麼東西都想要塗色。今天他拿到了一棵 N 個點的樹,其中 1 號是這棵樹的根,而且他手上有 K 種不同顏色的顏料,他想要把每個點都塗上這 K 種顏色其中的一種,並且滿足以下條件:對於任意兩個節點 x,y,他們的最低公共祖先被塗上的顏色要和 x,y 其中之一一樣。請幫小風算算看他有多少種不同的塗色方式吧!
輸入第一行有兩個正整數 N,K,代表這棵樹有 N 個點且小風有 K 種不同的顏料。
接下來 N−1 行每一行有兩個正整數 x,y,代表樹上的一條邊。
對於每一組輸入,請輸出一個整數代表有多少種不同的塗色方法滿足條件,請輸出答案mod109+7。
在一棵樹上,兩個點 x,y 的最低公共祖先是兩個點分別到根節點的路徑上深度最大的共同節點。
IOICamp 2020 Day2 pC