https://ac.nowcoder.com/acm/problem/15748
题意：
有n个节点n-1条边，由s节点开始，之后每次选择的节点不能选择之前的选择过的节点及其相邻节点。

分析：
n个节点，n-1条边，由s节点开始选择，很明显是一颗以s节点为根节点的树，这是一道树的最大独立集问题，由于n数据有5e5，显然根据数进行暴力搜索可能不太行，我们要用dp对它进行优化，这就是所谓的树形dp了，对树进行动态规划，对此题而言，由子节点推到父节点，即根的子节点传递有用的信息给父节点，最终由父节点再求出最优解。
而每一步的状态只有选择住宿还是不住宿（取或者不取），因此状态转移方程为：
dp[u][0/1] 表示以u为根的子树可以选择的最多的节点数,0表示不选u节点，1表示选择u节点。
dp[u][1]+=dp[t][0];//选择u节点，前面的节点的最优解加上1（当前节点）
dp[u][0]+=max(dp[t][1],dp[t][0]);//不选择u节点，max（选择子节点，不选择子节点）
因此答案为dp[s][1]

代码：

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<vector>
using namespace std;
typedef long long ll;
int i,j,n,k,tt,m,t,x,s,y;
vector<int>v[500005];
int dp[500005][2];
void dfs(int u,int fa){
    dp[u][1]=1;//选择u节点至少为1
    for(auto t:v[u]){
        if(t==fa){
            continue;
        }
        dfs(t,u);//递归到叶子节点
        dp[u][1]+=dp[t][0];//选择u节点
        dp[u][0]+=max(dp[t][1],dp[t][0]);//不选择u节点
    }
}
int main()
{
    scanf("%d%d",&n,&s);
    for(i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }   
    dfs(s,0);
    printf("%d",dp[s][1]);
}