题意:



思路:
%E8%A1%A8%E7%A4%BA%E5%9C%A8u%E4%B8%BA%E6%A0%B9%E7%9A%84%E5%AD%90%E6%A0%91%E4%B8%AD%EF%BC%8C%E9%80%89%2F%E4%B8%8D%E9%80%89u%E4%BD%8F%E5%AE%BF%EF%BC%8C%E6%9C%80%E5%A4%9A%E8%83%BD%E6%97%85%E6%B8%B8%E5%87%A0%E5%A4%A9&preview=true)

%20%3D%201%20%2B%20%5Csum%20dp(v%2C0)%2Cv%E2%88%88son_u&preview=true)

%20%3D%20max(%5Cquad%20dp(v%2C1)%5Cquad%20%2Cdp(v%2C0)%5Cquad)%2Cv%E2%88%88son_u&preview=true)
&preview=true)
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 5e5 + 10;
struct Node{
int to,nex;
}e[N << 1];
int n,s,head[N],idx;
int dp[N][2];
void add_edge(int u,int v){
e[idx].to = v;
e[idx].nex = head[u];
head[u] = idx++;
}
void dfs(int u,int fa){
dp[u][1] = 1;
for(int i = head[u];~i;i = e[i].nex){
int v = e[i].to;
if(v == fa) continue;
dfs(v,u);
dp[u][0] += max(dp[v][1],dp[v][0]);
dp[u][1] += dp[v][0];
}
}
int main(){
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&s);
for(int i = 1,u,v;i < n;i++){
scanf("%d%d",&u,&v);
add_edge(u,v);
add_edge(v,u);
}
dfs(s,-1);
printf("%d\n",dp[s][1]);
return 0;
}