题目大意：$NOIP2018\;TG\;D1T3$
题解：题目要求最短的赛道的长度最大，可以想达到二分答案，接着就是一个显然的树形$DP$。
发现对于一个点，它子树中若有两条链接起来比要求的答案大，一定接起来成为一条路径，因为接起来答案一定加一，而传递上去的话不一定。然后对于一条链，一定是找可行的最短的链与它相接，把尽可能长的链传递上去。找最小的可行的链我使用了双向链表（复杂度$O(n)$，右端点总共最多向左移动$n$次，每次最多向右移动$1$次）
卡点：考场上写结束后删除节点后转移到下一个节点时，没有考虑到移动到的节点也被删除的情况（考场上我是真的傻）
C++ Code：
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cctype>
namespace R {
int x, ch;
inline int read() {
ch = getchar();
while (isspace(ch)) ch = getchar();
for (x = ch & 15, ch = getchar(); isdigit(ch); ch = getchar()) x = x * 10 + (ch & 15);
return x;
}
}
using R::read;
#define maxn 50010
const int TANG_Yx = 20040826;
inline int max(int a, int b) {return a > b ? a : b;}
int head[maxn], cnt;
struct Edge {
int to, nxt, w;
} e[maxn << 1];
inline void add(int a, int b, int c) {
e[++cnt] = (Edge) {b, head[a], c}; head[a] = cnt;
}
int n, m, sum, ans;
int k, f[maxn];
inline bool debug(int k) {return true;}
int pre[maxn], nxt[maxn];
std::vector<int> V[maxn];
int dfn[maxn], rnk[maxn], idx, fa[maxn];
int up[maxn];
void dfs1(int u, int fa = 0) {
::fa[u] = fa; rnk[u] = u;
dfn[u] = ++idx;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (v != fa) {
up[v] = e[i].w;
dfs1(v, u);
}
}
}
inline void work(int u, int fa) {
std::vector<int> &V = ::V[u];
std::sort(V.begin(), V.end());
int sz = V.size();
while (sz && V[sz - 1] >= k) f[u]++, sz--;
int l = 0, r = 1, rem = 0;
if (sz > 0) {
#define End sz
#define Begin (sz + 1)
for (register int i = 0; i < sz; i++) {
pre[i] = i - 1;
nxt[i] = i + 1;
}
nxt[Begin] = 0;
pre[0] = Begin;
nxt[sz - 1] = End;
pre[End] = sz - 1;
while (r < End && l < r) {
while (nxt[r] < End && V[l] + V[r] < k) r = nxt[r];
while (pre[r] > l && pre[r] != Begin && V[l] + V[pre[r]] >= k) r = pre[r];
if (V[l] + V[r] >= k) {
f[u]++;
nxt[pre[l]] = nxt[l];
pre[nxt[l]] = pre[l];
nxt[pre[r]] = nxt[r];
pre[nxt[r]] = pre[r];
if (nxt[pre[l]] != End && pre[nxt[r]] != Begin && pre[nxt[r]] > nxt[pre[l]]) r = pre[nxt[r]];
else r = nxt[r];
l = nxt[pre[l]];
} else l = nxt[l];
if (l == r) r = nxt[r];
}
if (0 <= pre[End] && pre[End] < sz) rem = V[pre[End]];
else rem = 0;
#undef End
#undef Begin
}
if (u != 1) {
::V[fa].push_back(rem + up[u]);
f[fa] += f[u];
}
}
inline bool check(int mid) {
k = mid;
for (register int i = 1; i <= n; i++) V[i].clear(), f[i] = 0;
for (register int I = 1, i = rnk[I]; I <= n; i = rnk[++I]) {
work(i, fa[i]);
}
return f[1] >= m;
}
namespace Work1 {
int MAX, ans;
void dfs(int u, int fa = 0, int dep = 0) {
if (dep > MAX) {
MAX = dep;
ans = u;
}
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (v != fa) {
dfs(v, u, dep + e[i].w);
}
}
}
int main() {
MAX = 0;
dfs(1);
int x = ans;
MAX = 0;
dfs(x);
printf("%d\n", MAX);
return 0;
}
}
namespace Work2 {
int pre[maxn];
void dfs(int u, int fa = 0) {
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (v != fa) {
pre[v] = pre[u] + e[i].w;
dfs(v, u);
}
}
}
bool check(int mid) {
int last = 0, res = 0;
for (int i = 1; i <= n; i++) {
if (pre[i] - last >= mid) {
last = pre[i];
res++;
}
}
return res >= m;
}
int main() {
dfs(1);
int l = 1, r = sum / m, ans = 0;
while (l <= r) {
int mid = l + r >> 1;
if (check(mid)) {
l = mid + 1;
ans = mid;
} else r = mid - 1;
}
printf("%d\n", ans);
return 0;
}
}
inline bool cmp(int a, int b) {return dfn[a] > dfn[b];}
bool flag = true;
int main() {
n = read(), m = read();
for (int i = 1, a, b, c; i < n; i++) {
a = read(), b = read(), c = read();
add(a, b, c);
add(b, a, c);
if (a - b != 1 && b - a != 1) flag = false;
sum += c;
}
if (m == 1) {
return Work1::main();
}
if (flag) {
return Work2::main();
}
dfs1(1);
std::sort(rnk + 1, rnk + n + 1, cmp);
int l = 1, r = sum / m;
while (l <= r) {
int mid = l + r >> 1;
if (check(mid)) {
l = mid + 1;
ans = mid;
} else r = mid - 1;
}
printf("%d\n", ans);
return 0;
}