Solutions of Tree coloring 2

Select solution language

Hiiragi_Sergan Created at 0 likes

### 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; }