题解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
using pl = pair<ll, ll>;

#define pb push_back
#define f first
#define s second

const ll MAXN = 1e5, INF = 1e9;

vl adj[MAXN];

int main() {
	ll n, k;
	cin >> n >> k;
	--k;
	for (int i = 0; i < n - 1; i++) {
		ll a, b;
		cin >> a >> b;
		--a, --b;
		adj[a].pb(b), adj[b].pb(a);
	}
	vl dist1(n, INF), dist2(n, INF);
	dist2[k] = 0;
	queue<ll> q;
	q.push(k);
	while (!q.empty()) {
		ll cur = q.front();
		q.pop();
		for (ll u : adj[cur]) {
			if (dist2[cur] + 1 < dist2[u]) {
				dist2[u] = dist2[cur] + 1;
				q.push(u);
			}
		}
	}

	for (int i = 0; i < n; i++) {
		if (adj[i].size() == 1) {
			q.push(i);
			dist1[i] = 0;
		}
	}
	while (!q.empty()) {
		ll cur = q.front();
		q.pop();
		for (ll u : adj[cur]) {
			if (dist1[cur] + 1 < dist1[u]) {
				dist1[u] = dist1[cur] + 1;
				q.push(u);
			}
		}
	}

	ll res = 0;
	q.push(k);
	vl vis(n);
	while (!q.empty()) {
		ll cur = q.front();
		q.pop();
		if (dist1[cur] <= dist2[cur]) {
			res++;
			continue;
		}
		if (vis[cur]) { continue; }
		vis[cur] = true;
		for (ll u : adj[cur]) { q.push(u); }
	}
	cout << res << endl;
}