Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stdio.h>
- #include <fstream>
- #include <queue>
- #include <iomanip>
- #include <cstdio>
- #include <string>
- #include <cmath>
- #include <algorithm>
- #include <vector>
- #include <time.h>
- #include <cassert>
- #include <map>
- #include <set>
- #include <stack>
- #include <time.h>
- #include <cstdlib>
- #include <cstring>
- #include <string.h>
- #include <bitset>
- #include <ctype.h>
- #include <complex>
- //#include <unordered_map>
- //#include <unordered_set>
- #define llong long long int
- #define pb push_back
- #define mp make_pair
- #define pr pair <int, int>
- #define X first
- #define Y second
- #define endl "\n"
- using namespace std;
- const int MAXN = 1e6 + 50;
- const int INF = 1e9 + 7;
- //const llong LINF = 1e18;
- const int MOD = 1e9 + 7;
- int n, d;
- vector<int> a[MAXN];
- int depth[MAXN];
- int component[MAXN];
- int get(int x) {
- if (component[x] == x) {
- return x;
- }
- return component[x] = get(component[x]);
- }
- inline void do_uninon(int x, int y) {
- x = get(x);
- y = get(y);
- if (x != y)
- component[x] = y;
- }
- int getdiameter(int x, int p = -1) {
- if (p != -1) {
- depth[x] = depth[p] + 1;
- } else {
- depth[x] = 0;
- }
- int cur = x;
- for (auto i: a[x]) {
- if (i != p) {
- int tmp = getdiameter(i, x);
- if (depth[tmp] > depth[cur]) {
- cur = tmp;
- }
- }
- }
- return cur;
- }
- int level[MAXN], whoonthislevel[MAXN];
- int mx[MAXN];
- vector<int> v[MAXN];
- void dfs(int x, int p = -1) {
- v[x].clear();
- if (p == -1) {
- level[x] = 0;
- } else {
- level[x] = level[p] + 1;
- }
- whoonthislevel[level[x]] = x;
- if (level[x] >= d) {
- do_uninon(x, whoonthislevel[level[x] - d]);
- }
- mx[x] = level[x];
- for (auto i: a[x]) {
- if (i == p) {
- continue;
- }
- dfs(i, x);
- if (v[x].size() < v[i].size()) {
- swap(v[x], v[i]);
- swap(mx[x], mx[i]);
- }
- for (auto j: v[i]) {
- int c = level[j] - level[x];
- if (c < d && level[x] >= c && mx[x] - level[x] >= d - c) {
- do_uninon(j, whoonthislevel[level[x] - c]);
- }
- v[x].pb(j);
- }
- mx[x] = max(mx[x], mx[i]);
- }
- v[x].pb(x);
- }
- int main() {
- #ifdef DEBUG
- double beg = clock();
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #else
- //freopen("sump.in", "r", stdin);
- //freopen("sump.out", "w", stdout);
- #endif
- //ios_base::sync_with_stdio(0);cin.tie();
- scanf("%d%d", &n, &d);
- for (int i = 1; i < n; i++) {
- int x, y;
- scanf("%d%d", &x, &y);
- a[x].pb(y);
- a[y].pb(x);
- }
- for (int i = 1; i <= n; i++) {
- component[i] = i;
- }
- int D1 = getdiameter(1);
- int D2 = getdiameter(D1);
- dfs(1);
- dfs(D1);
- dfs(D2);
- int ans = 0;
- for (int i = 1; i <= n; i++) {
- int x = get(i);
- if (x == i) {
- ans++;
- }
- }
- cout << ans;
- #ifdef DEBUG
- double end = clock();
- fprintf(stderr, "\n*** Total time = %.3lf ***\n", (end - beg) / CLOCKS_PER_SEC);
- #endif
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement