可以用树型dp，对于某一个结点，是否选择这个点进入集合，我们用dp数组表示，dp[i][0]dp[i][0]表示以ii结点为根的子树，不选取该结点时的最大独立集的数量，dp[i][1]dp[i][1]则表示以ii结点为根的子树，选取该结点时的最大独立集的数量，那么dfs构建这个dp数组以后，dp[s][1]dp[s][1]就是我们需要的答案了。

我们dfs遍历树，构建这个dp数组，每次先进入子树，算子树的dp，然后轮到自己，如果选取了这个结点本身，那么与该节点相邻的结点都不能选，dp[cur][1]+=dp[next][0]dp[cur][1]+=dp[next][0]，如果没有选取该结点本身，对于子节点可以选也可以不选，我们取最大值即可，dp[cur][0]+=max(dp[next][1],dp[next][0])dp[cur][0]+=max(dp[next][1],dp[next][0])。因为一个结点可能有多个子节点，子节点的子树之间不会相邻，因此是累加。

#include<iostream>
#include<vector>
using namespace std;

int dp[500001][2];
vector<int> G[500001];

void dfs(int cur, int pre){
    for(int i = 0; i < G[cur].size(); i++){ //遍历所有子节点
        int next = G[cur][i];
        if(next == pre) //不能重复遍历
            continue;
        dfs(next, cur); //进入子树
        dp[cur][0] += max(dp[next][1],dp[next][0]); //不选该结点时，取子节点最大值
        dp[cur][1] += dp[next][0]; //该结点选了自己，不能选相邻的子结点
    }
}

int main(){
    int n, s;
    cin >> n >> s;
    for(int i = 1; i <= n; i++) //初始化每个结点都选取自己的情况
        dp[i][1] = 1;
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        G[u].push_back(v); //构建树
        G[v].push_back(u);
    }
    dfs(s, -1); //dfs遍历树
    cout << dp[s][1] << endl; 
    return 0;
}