Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define MAXN 212345
- #define inf 0x3f3f3f3f
- typedef pair<int,int> pii;
- vector<int> graph[MAXN];
- int n, k, maxh, num;
- int ans[MAXN], sz[MAXN], hsum[MAXN], subtree_hsum[MAXN];
- bool block[MAXN];
- int dfs1(int a, int p)
- {
- sz[a] = 1;
- for(int i = 0; i < graph[a].size(); i++)
- if(graph[a][i] != p && !block[graph[a][i]])
- sz[a] += dfs1(graph[a][i], a);
- return sz[a];
- }
- void dfs2(int a, int p, pii &res)
- {
- int mx = num - sz[a];
- for(int i = 0; i < graph[a].size(); i++)
- if(graph[a][i] != p && !block[graph[a][i]])
- {
- mx = max(mx, sz[graph[a][i]]);
- dfs2(graph[a][i], a, res);
- }
- if(mx < res.first)
- res = pii(mx, a);
- }
- int find_centroid(int a)
- {
- num = dfs1(a, a);
- pair<int,int> res(inf, 0);
- dfs2(a, a, res);
- return res.second;
- }
- void dfs3(int a, int p, int h, int vec[])
- {
- maxh = max(h, maxh);
- vec[h]++;
- for(int i = 0; i < graph[a].size(); i++)
- if(graph[a][i] != p && !block[graph[a][i]])
- dfs3(graph[a][i], a, h+1, vec);
- }
- void dfs4(int a, int p, int h)
- {
- if(h > k)
- return;
- ans[a] += hsum[min(num, k - h)] - subtree_hsum[min(maxh, k - h)];
- for(int i = 0; i < graph[a].size(); i++)
- if(graph[a][i] != p && !block[graph[a][i]])
- dfs4(graph[a][i], a, h+1);
- }
- void decomp(int a)
- {
- a = find_centroid(a);
- maxh = 0;
- num = dfs1(a, a);
- memset(hsum, 0, sizeof(int) * (num + 1));
- dfs3(a, a, 0, hsum);
- for(int i = 1; i <= num; i++)
- hsum[i] += hsum[i-1];
- ans[a] += hsum[min(num, k)];
- for(int i = 0; i < graph[a].size(); i++)
- if(!block[graph[a][i]])
- {
- memset(subtree_hsum, 0, sizeof(int) * (sz[graph[a][i]] + 1));
- maxh = 0;
- dfs3(graph[a][i], a, 1, subtree_hsum);
- for(int j = 1; j <= maxh; j++)
- subtree_hsum[j] += subtree_hsum[j-1];
- dfs4(graph[a][i], a, 1);
- }
- block[a] = true;
- for(int i = 0; i < graph[a].size(); i++)
- if(!block[graph[a][i]])
- decomp(graph[a][i]);
- }
- int main(void)
- {
- int a, b;
- scanf("%d %d", &n, &k);
- for(int i = 1; i < n; i++)
- {
- scanf("%d %d", &a, &b);
- graph[a].push_back(n+i);
- graph[n+i].push_back(b);
- graph[b].push_back(n+i);
- graph[n+i].push_back(a);
- }
- decomp(1);
- int retv = 0;
- if(k%2 == 0)
- for(int i = 1; i <= n; i++)
- retv = max(retv, ans[i]);
- else
- for(int i = n+1; i < 2*n; i++)
- retv = max(retv, ans[i]);
- printf("%d\n", (retv + 1) / 2);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement