- #include < algorithm > #include < iostream > #include < cstring > #include < cstdio > using namespace std;
- inline int read() {
- int sum(0);
- char ch(getchar());
- for (; ch < ‘0‘ || ch > ‘9‘; ch = getchar());
- for (; ch >= ‘0‘ && ch <= ‘9‘; sum = sum * 10 + (ch ^ 48), ch = getchar());
- return sum;
- }
- struct edge {
- int e;
- edge * n;
- }
- a[200005],
- *pre[100005];
- int tot;
- inline void insert(int s, int e) {
- a[++tot].e = e;
- a[tot].n = pre[s];
- pre[s] = &a[tot];
- }
- int n,
- m;
- int f[100005],
- fa[100005];
- int ans;
- int mid,
- num;
- int tmp[100005];
- inline bool cmp(int x, int y) {
- return x > y;
- }
- inline void dfs(int u) {
- bool flag(false);
- for (edge * i = pre[u]; i; i = i - >n) {
- int e(i - >e);
- if (e != fa[u]) {
- flag = true;
- fa[e] = u;
- dfs(e);
- }
- }
- if (!flag) return;
- tmp[0] = 0;
- f[u] = 0;
- for (edge * i = pre[u]; i; i = i - >n) {
- int e(i - >e);
- if (e != fa[u]) tmp[++tmp[0]] = f[e] + 1;
- }
- int size(tmp[0]);
- sort(tmp + 1, tmp + 1 + size, cmp);
- tmp[size + 1] = 0;
- for (int i = 1; i <= size; ++i) {
- if (tmp[i] + tmp[i + 1] > mid)++num;
- else {
- f[u] = tmp[i];
- break;
- }
- }
- }
- inline bool check() {
- num = 0;
- memset(f, 0, sizeof(f));
- dfs(1);
- if (num <= m) return true;
- return false;
- }
- inline void ef(int l, int r) {
- while (l <= r) {
- mid = (l + r) >> 1;
- if (check()) r = mid - 1,
- ans = mid;
- else l = mid + 1;
- }
- }
- int main() {
- memset(pre, NULL, sizeof(pre));
- n = read(),
- m = read();
- for (int i = 1; i < n; ++i) {
- int x(read()),
- y(read());
- insert(x, y),
- insert(y, x);
- }
- ef(1, n);
- printf("%d", ans);
- }
来源: http://www.bubuko.com/infodetail-2304882.html