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;
}
```
tonblan
Created at
13 likes