Bzoj 2060(树形DP)

(BZOJ 2060)[http://www.lydsy.com/JudgeOnline/problem.php?id=2060]
luogu免权限地址
设状态$f[i][0]$为$i$点不访问,$f[i][1]$为$i$点访问

$f[u][1] += f[v][0] $ u点要访问,(u,v)有连边
$f[u][0] += max(f[v][0], f[v][1]) $ u点不访问,(u,v)有连边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define ms(i,j) memset(i,j, sizeof i);
using namespace std;
const int MAXN = 50000 + 5;
int n;
vector<int> G[MAXN];
int vi[MAXN];
int dp[MAXN][2];//0:不拜访i点 ,1:拜访i点
int dfs(int u)
{
dp[u][1] = 1;
for (int i=0;i<G[u].size();i++)
{
int v = G[u][i];
if(!vi[v])
{
vi[v] = true;
dfs(v);
dp[u][0] += max(dp[v][0], dp[v][1]);
dp[u][1] += dp[v][0];
}
}
}
int main()
{
scanf("%d", &n);
for (int i=1;i<n;i++)
{
int x,y;
scanf("%d%d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
ms(vi,false);ms(dp,0);vi[1] = true;//不要忘了节点1的访问数组赋值
dfs(1);
printf("%d\n", max(dp[1][0], dp[1][1]));
return 0;
}

------ 本文结束 ------