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)有连边

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