點燈
發布時間: June 27, 2024, 7:51 p.m. 最後更新時間: June 28, 2024, 7:53 a.m. 時間限制: 1000ms 記憶體限制: 128M
聖誕節快到了(?)
Colin買了一棵樹
想在上面裝上一些燈泡做裝飾營造些佳節氣氛
已知這棵樹有$n$個節點，編號為$1$~$n$，每個節點上都事先裝好一顆燈泡
但Colin沒什麼錢，為了節省電費，相鄰節點的燈泡不會同時點亮
請問點燈方法數總共有多少種？（至少要有一個節點的燈泡被點亮）
數字可能很大，請將答案模除$10^9+7$
第一行輸入一正整數$n$，表示節點數量，$1\le n\le 2\times 10^5$
接下來$n-1$行，每行輸入兩正整數$a,b$，表示此二節點間有邊連接
輸出一正整數$ans$，表示點燈方法數（模除$10^9+7$）
複製範例
5 1 2 1 3 2 4 2 5
13
複製範例
3 1 2 1 3
4
