827 . 塗色問題
TopCoder
Description
小桃有一棵 $N$ 個點的樹，節點的編號為 $1, 2, \ldots, N$。她想要在這棵樹的每個節點塗上紅色、藍色或綠色這三種顏色之一，然而她不希望一條邊兩端點的顏色一樣，請問她有幾種上色的方式？由於這個數字可能太大，請輸出方法數除以 $10^ 9 + 7$ 後的餘數。
Input Format
輸入第一行有一個正整數 $N$，代表樹的節點數量
接下來的 $N - 1$ 每行有兩個正整數 $u, v$，代表節點 $u$ 與節點 $v$ 之間有一條邊。
- $1 \leq N \leq 200000$
- $1 \leq u, v \leq N$
- 保證輸入是一棵樹
Output Format
輸出一行一個整數，代表塗色的方法數除以 $10^ 9 + 7$ 後的餘數。
Sample Input 1
3
1 2
2 3
1 2
2 3
Sample Output 1
12
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~21 | 無額外限制 | 100 |