Solutions of Tree coloring

Select solution language

tonblan Created at 13 likes

Giả sử chọn gốc của cây tại 1, ta sẽ tiến hành quy hoạch động trên cây với ý tưởng như sau: tại một đỉnh **u** bất kì, ta có hai lựa chọn tô màu đỉnh này hoặc không. Gọi trạng thái quy hoạch động dp[u][0] là không tô màu đỉnh này, dp[u][1] là có tô màu đỉnh. Với trường hợp không tô màu đỉnh này, có con bất kì của đỉnh **u** là *v*, tổng số cách sẽ là tổng các max(dp[v][0], dp[v][1]) vì đỉnh **u** không tô màu, việc lấy đỉnh *v* tô màu hay không không quan trọng. Còn trường hợp đỉnh **u** tô màu thì số cách sẽ là tổng của các dp[v][0], vì đỉnh u tô màu nên chỉ lấy các trường hợp đỉnh con *v* không tô màu

$#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int n, dp[N][2]; vector<int> adj[N]; void dfs(int u, int par){ for(auto v : adj[u]){ if(v != par){ dfs(v, u); dp[u][0] += max(dp[v][0], dp[v][1]); dp[u][1] += dp[v][0]; } } } int32_t main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for(int i = 1;i < n;++i){ int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } memset(dp, 0, sizeof(dp)); for(int i = 1;i <= n;++i){ dp[i][1] = 1; } dfs(1, 0); cout << max(dp[1][0], dp[1][1]); return 0; }$