酸欠少女
小桃有一棵 N 個點的樹,節點的編號為 1,2,…,N。她想要在這棵樹的每個節點塗上紅色、藍色或綠色這三種顏色之一,然而她不希望一條邊兩端點的顏色一樣,請問她有幾種上色的方式?由於這個數字可能太大,請輸出方法數除以 109+7 後的餘數。
輸入第一行有一個正整數 N,代表樹的節點數量
接下來的 N−1 每行有兩個正整數 u,v,代表節點 u 與節點 v 之間有一條邊。
輸出一行一個整數,代表塗色的方法數除以 109+7 後的餘數。