827 . 塗色問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

100.0% (6/6)

Submission's AC Ratio

31.6% (6/19)

Tags

apcsc apcsc-dp

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

Sample Output 1

12

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~21 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
Submit
Back to Top