1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
| #include <bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
#define PLL pair<LL, LL>
using namespace std;
template <class T>
inline void read(T &res)
{
res = 0;
bool flag = 0;
char c = getchar();
while (c < '0' || '9' < c) { if (c == '-') flag = 1; c = getchar(); }
while ('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
if (flag) res = -res;
}
template <class T, class... ARC>
inline void read(T &res, ARC &...com) { read(res), read(com...); }
template <class T>
void write(T res)
{
if (res < 0)
putchar('-'), res = -res;
if (res > 9)
write(res / 10);
putchar(res % 10 + '0');
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(const char *s) { while (*s) putchar(*s++); }
template <class T, class... ARC>
inline void write(T res, ARC... com) { write(res), write(com...); }
const int N = 2e5 + 5;
int n, m;
int idx;
int e[N << 1], ne[N << 1], h[N];
inline void add(int x, int y)
{
idx ++;
e[idx] = y, ne[idx] = h[x], h[x] = idx;
}
int cnt, dfn[N], len, type[N];
void dfs(int x, int y)
{
dfn[x] = 0, type[x] = 1;
int res = 0, maxn = 0;
for(int i = h[x], j; ~i;i = ne[i])
{
j = e[i];
if(j == y) continue;
dfs(j, x);
res = min(res, dfn[j]);
maxn = max(maxn, dfn[j] + type[j]);
}
if(res + maxn + 1 <= 0 && res < 0) dfn[x] = res + 1, type[x] = 0;
else{
if(maxn < len) dfn[x] = maxn;
else dfn[x] = -len, cnt ++, type[x] = 0;
}
}
inline bool check(int mid)
{
cnt = 0, len = mid;
dfs(1, 1);
if(dfn[1] > 0 || type[1]) cnt ++;
return cnt <= m;
}
int main()
{
memset(h, -1, sizeof(h));
read(n, m);
for(int i = 1, o, u;i < n;i ++) read(o, u), add(o, u), add(u, o);
int l = 0, r = n, k;
while(l <= r)
{
int mid = l + r >> 1;
if(check(mid)) r = mid - 1, k = mid;
else l = mid + 1;
}
write(k);
return 0;
}
|