题解 | 旅游

//  #牛客春招刷题训练营# https://www.nowcoder.com/discuss/726480854079250432
//  思路来自其它题解，建议找到题解中阅读量最高的哪个读一遍，然后对照着敲先全局，再main遇到自定义函数时可以先把main敲完也可以跳到自定义函数部分
//  因为n个点n-1个边且互相连通所以不会有环
#include <iostream>
#include <vector>
using namespace std;

int dp[500001][2];
vector<int> G[500001];//--------用于建立邻接表


void dfs(int cur, int pre){//----------我是跟着原题解敲的，那里就叫dfs虽然我也不懂
  for (int i = 0; i < G[cur].size();i++){//-----遍历子树，树状dp
    int next = G[cur][i];
    if (next == pre) continue;//-------pre是当前节点的父节点，不能往回走成死循环
    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);
  cout << dp[s][1] << endl;
  return 0;
}