### Nhận xét:
* Với mỗi đỉnh v (trừ đỉnh gốc) đều có một đỉnh cha u nối liền
* --> Ta còn lại 2 cách chọn màu cho đỉnh v, sao cho không trùng màu với đỉnh u
---
### Trường hợp cơ sở & Công thức truy hồi:
* Gọi `dp[u]` là **số cách tô màu thỏa mãn** đến đỉnh u
* Trường hợp cơ sở:
Đỉnh gốc (đỉnh 1) có thể chọn tự do 1 trong 3 màu
--> dp[1] = 3
Các đỉnh còn lại chỉ còn 2 cách chọn màu (không trùng màu với đỉnh cha)
--> v ∈ [2..n] : dp[v] = 2
* Công thức truy hồi:
Vì mỗi đỉnh con `v` có dp[v] cách tô màu (khác màu cha) và các cách tô màu là **độc lập** nên ta sẽ nhân các cách lại
--> dp[u] = dp[u] * dp[v1] * dp[v2] * dp[v3] * ... dp[vk]
---
### Code mẫu:
```cpp
void dfs(int u, int par){
for (int v : node[u]){
if(v != par){
dfs(v, u);
dp[u] = (dp[u] * dp[v]) % MOD;
}
}
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
REP(i, 1, n-1){
cin >> u >> v;
node[u].push_back(v);
node[v].push_back(u);
}
REP(i, 1, n) dp[i] = 2;
dp[1] = 3;
dfs(1, -1);
cout << dp[1];
return 0;
}