Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 100005;
- int n, k;
- vector <int> g[N];
- int nearest[N];
- void calc(int v, int par) {
- if (g[v].size() == 1) {
- nearest[v] = 0;
- return;
- }
- nearest[v] = n + 1;
- for (int i : g[v]) {
- if (i != par) {
- calc(i, v);
- nearest[v] = min(nearest[v], nearest[i] + 1);
- }
- }
- }
- int res = 0;
- void dfs(int v, int par, int d) {
- if (nearest[v] <= d) {
- res++;
- return;
- }
- for (int i : g[v]) {
- if (i != par) {
- dfs(i, v, d + 1);
- }
- }
- }
- int main() {
- ios_base :: sync_with_stdio(0);
- cin.tie(0), cout.tie(0);
- freopen("atlarge.in", "r", stdin);
- freopen("atlarge.out", "w", stdout);
- cin >> n >> k;
- for (int i = 1, a, b; i < n; i++) {
- cin >> a >> b;
- g[a].push_back(b), g[b].push_back(a);
- }
- calc(k, -1); /// one small thing to notice: if k itself is a leaf, then the values for nearest will not be calculated as the function will stop, but in this case answers is 1, which is calculated correctly regardless. anyway, for getting proper nearest values, just starting the dfs from any non-leaf point is ok.
- dfs(k, -1, 0);
- cout << res << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment