思路

• 二分答案：对 $D$ 二分，检查是否能用不超过 $k$ 次删边，使所有连通块直径 $\le D$。

• 可行性检查（贪心 + 树形 DP，自底向上）：

  • 固定根（任意如 1），一次性预处理父子关系与后序序列。

  • 对每个节点，把每个子树向上“贡献”的路径长度记为 $t = \text{up}[v] + w(u,v)$。

    • 若 $t > D$，该子边必须切断（计一次删除）。
    • 否则加入数组 $A$。

  • 为保证以该节点为“拐点”的路径不超标，数组 $A$ 中任意两条保留路径的和必须 $\le D$。这等价于只需保证最大两条之和 $\le D$。因此：

    • 将 $A$ 排序；当 $|A|\ge 2$ 且 $A[-1]+A[-2] > D$ 时，不断删除最大的那条并计数（贪心最优）。
    • 该节点向父节点仅需保留一条“向上路径”，取当前最大者：$\text{up}[u] = A[-1]$（若 $A$ 为空则为 0）。

• 如此统计到根的总删除次数 $\text{cuts}$，判断 $\text{cuts} \le k$ 即可。

• 直径上界：用两次 DFS/栈求树的加权直径，作为二分上界；下界为 0。

以上贪心正确性要点：在某节点仅需约束“最大两条”之和；若违反则优先删除更大的那条能使未来冲突概率最小，从而删边数最少。

C++

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct Edge { int to; ll w; };

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n; int k;
	if (!(cin >> n >> k)) return 0;
	vector<vector<Edge>> g(n + 1);
	for (int i = 0; i < n - 1; ++i) {
		int u, v; ll w;
		cin >> u >> v >> w;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}

	// 计算加权直径作为二分上界
	auto farthest = [&](int start) {
		vector<ll> dist(n + 1, -1);
		vector<int> st;
		st.reserve(n);
		st.push_back(start);
		dist[start] = 0;
		vector<int> parent(n + 1, -1);
		while (!st.empty()) {
			int u = st.back(); st.pop_back();
			for (auto &e : g[u]) {
				int v = e.to;
				if (v == parent[u]) continue;
				parent[v] = u;
				dist[v] = dist[u] + e.w;
				st.push_back(v);
			}
		}
		int idx = 1;
		for (int i = 1; i <= n; ++i) if (dist[i] > dist[idx]) idx = i;
		return pair<int,ll>(idx, dist[idx]);
	};
	int a = farthest(1).first;
	auto [b, dia] = farthest(a);

	// 预处理：固定根1，建立父子关系、parent边权、后序序列
	vector<int> parent(n + 1, 0);
	vector<ll> pw(n + 1, 0);           // 与父亲相连的边权
	vector<vector<int>> children(n + 1);
	vector<int> post; post.reserve(n);

	{
		// 迭代式DFS生成后序
		vector<pair<int,int>> st;
		st.reserve(2*n);
		parent[1] = 0; pw[1] = 0;
		st.push_back({1, 0}); // 0: 进入, 1: 退出
		while (!st.empty()) {
			auto [u, t] = st.back(); st.pop_back();
			if (t == 0) {
				st.push_back({u, 1});
				for (auto &e : g[u]) {
					int v = e.to;
					if (v == parent[u]) continue;
					parent[v] = u;
					pw[v] = e.w;
					children[u].push_back(v);
					st.push_back({v, 0});
				}
			} else {
				post.push_back(u);
			}
		}
	}

	vector<ll> up(n + 1, 0);

	auto feasible = [&](ll D) -> bool {
		long long cuts = 0;
		for (int idx = (int)post.size() - 1; idx >= 0; --idx) {
			int u = post[idx];
			vector<ll> A;
			A.reserve(children[u].size());
			for (int v : children[u]) {
				ll t = up[v] + pw[v];
				if (t > D) {
					// 必须切断这条边
					++cuts;
				} else {
					A.push_back(t);
				}
			}
			sort(A.begin(), A.end());
			while ((int)A.size() >= 2 && A.back() + A[(int)A.size() - 2] > D) {
				A.pop_back();
				++cuts;
			}
			up[u] = A.empty() ? 0LL : A.back();
			if (cuts > k) return false; // 剪枝
		}
		return cuts <= k;
	};

	ll lo = 0, hi = dia;
	while (lo < hi) {
		ll mid = (lo + hi) >> 1;
		if (feasible(mid)) hi = mid;
		else lo = mid + 1;
	}
	cout << lo << "\n";
	return 0;
}

Python

import sys
sys.setrecursionlimit(1 << 25)
data = sys.stdin.buffer.read().split()
it = iter(data)
n = int(next(it)); k = int(next(it))

# 邻接表：g[u] = [(v, w), ...]
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	u = int(next(it)); v = int(next(it)); w = int(next(it))
	g[u].append((v, w))
	g[v].append((u, w))

# 计算加权直径
def farthest(start: int):
	dist = [-1] * (n + 1)
	parent = [-1] * (n + 1)
	st = [start]
	dist[start] = 0
	while st:
		u = st.pop()
		for v, w in g[u]:
			if v == parent[u]: continue
			parent[v] = u
			dist[v] = dist[u] + w
			st.append(v)
	idx = 1
	for i in range(1, n + 1):
		if dist[i] > dist[idx]:
			idx = i
	return idx, dist[idx]

a, _ = farthest(1)
b, dia = farthest(a)

# 固定根1，建立父子、父边权、后序序列
parent = [0] * (n + 1)
pw = [0] * (n + 1)       # 与父亲相连的边权
children = [[] for _ in range(n + 1)]
post = []

st = [(1, 0)]  # (u, state) 0: 进入, 1: 退出
parent[1] = 0; pw[1] = 0
while st:
	u, t = st.pop()
	if t == 0:
		st.append((u, 1))
		for v, w in g[u]:
			if v == parent[u]: continue
			parent[v] = u
			pw[v] = w
			children[u].append(v)
			st.append((v, 0))
	else:
		post.append(u)

up = [0] * (n + 1)

def feasible(D: int) -> bool:
	cuts = 0
	for u in reversed(post):
		A = []
		for v in children[u]:
			t = up[v] + pw[v]
			if t > D:
				cuts += 1
			else:
				A.append(t)
		A.sort()
		while len(A) >= 2 and A[-1] + A[-2] > D:
			A.pop()   # 删除最大的这条
			cuts += 1
		up[u] = A[-1] if A else 0
		if cuts > k:
			return False
	return cuts <= k

lo, hi = 0, dia
while lo < hi:
	mid = (lo + hi) // 2
	if feasible(mid):
		hi = mid
	else:
		lo = mid + 1

print(lo)

Java

import java.io.*;
import java.util.*;

/**
 * 二分 + 树形DP可行性检查（自底向上，贪心删除最大的分支直到最大两条之和 <= D）
 */
public class Main {
	static class FastScanner {
		BufferedInputStream in;
		byte[] buffer = new byte[1 << 16];
		int ptr = 0, len = 0;
		FastScanner(InputStream is) { in = new BufferedInputStream(is); }
		int read() throws IOException {
			if (ptr >= len) {
				len = in.read(buffer); ptr = 0;
				if (len <= 0) return -1;
			}
			return buffer[ptr++];
		}
		int nextInt() throws IOException {
			int c, s = 1, x = 0;
			do { c = read(); } while (c <= ' ');
			if (c == '-') { s = -1; c = read(); }
			while (c > ' ') { x = x * 10 + (c - '0'); c = read(); }
			return x * s;
		}
	}
	static int n, k, m, idx;
	static int[] head, to, next, parent;
	static long[] w, pw, up;
	static ArrayList<Integer>[] children;
	static int[] post; // 后序
	static int postPtr;

	static void addEdge(int u, int v, int ww) {
		to[idx] = v; w[idx] = ww; next[idx] = head[u]; head[u] = idx++;
	}

	static int farthestNode(int start) {
		long[] dist = new long[n + 1];
		Arrays.fill(dist, -1);
		int[] par = new int[n + 1];
		Arrays.fill(par, -1);
		int[] st = new int[n];
		int top = 0;
		st[top++] = start;
		dist[start] = 0;
		while (top > 0) {
			int u = st[--top];
			for (int e = head[u]; e != -1; e = next[e]) {
				int v = to[e];
				if (v == par[u]) continue;
				par[v] = u;
				dist[v] = dist[u] + w[e];
				st[top++] = v;
			}
		}
		int idxNode = 1;
		for (int i = 1; i <= n; ++i) {
			if (dist[i] > dist[idxNode]) idxNode = i;
		}
		return idxNode;
	}

	static long farthestDist(int start) {
		long[] dist = new long[n + 1];
		Arrays.fill(dist, -1);
		int[] par = new int[n + 1];
		Arrays.fill(par, -1);
		int[] st = new int[n];
		int top = 0;
		st[top++] = start;
		dist[start] = 0;
		while (top > 0) {
			int u = st[--top];
			for (int e = head[u]; e != -1; e = next[e]) {
				int v = to[e];
				if (v == par[u]) continue;
				par[v] = u;
				dist[v] = dist[u] + w[e];
				st[top++] = v;
			}
		}
		long best = 0;
		for (int i = 1; i <= n; ++i) best = Math.max(best, dist[i]);
		return best;
	}

	static boolean feasible(long D) {
		long cuts = 0;
		// 自底向上处理
		for (int p = postPtr - 1; p >= 0; --p) {
			int u = post[p];
			int sz = children[u].size();
			long[] arr = new long[sz];
			int tsz = 0;
			for (int i = 0; i < sz; ++i) {
				int v = children[u].get(i);
				long t = up[v] + pw[v];
				if (t > D) {
					cuts++;
				} else {
					arr[tsz++] = t;
				}
			}
			if (tsz > 1) {
				Arrays.sort(arr, 0, tsz);
				while (tsz >= 2 && arr[tsz - 1] + arr[tsz - 2] > D) {
					tsz--; // 删除最大的
					cuts++;
				}
			}
			up[u] = (tsz > 0 ? arr[tsz - 1] : 0L);
			if (cuts > k) return false;
		}
		return cuts <= k;
	}

	public static void main(String[] args) throws Exception {
		FastScanner fs = new FastScanner(System.in);
		n = fs.nextInt(); k = fs.nextInt();
		m = 2 * (n - 1);
		head = new int[n + 1];
		to = new int[m];
		next = new int[m];
		w = new long[m];
		Arrays.fill(head, -1); idx = 0;
		for (int i = 0; i < n - 1; ++i) {
			int u = fs.nextInt(), v = fs.nextInt(), ww = fs.nextInt();
			addEdge(u, v, ww);
			addEdge(v, u, ww);
		}

		// 直径
		int a = farthestNode(1);
		long dia = farthestDist(a);

		// 固定根1，构建父子与后序
		parent = new int[n + 1];
		pw = new long[n + 1];
		children = new ArrayList[n + 1];
		for (int i = 1; i <= n; ++i) children[i] = new ArrayList<>();
		post = new int[n]; postPtr = 0;
		// 迭代DFS生成后序
		int[][] st = new int[2 * n][2]; // (u, state)
		int top = 0;
		st[top][0] = 1; st[top][1] = 0; top++;
		parent[1] = 0; pw[1] = 0;
		while (top > 0) {
			int u = st[--top][0];
			int state = st[top][1]; // 读取刚弹出的state
			if (state == 0) {
				// 重新压回退出态
				st[top][0] = u; st[top][1] = 1; top++;
				for (int e = head[u]; e != -1; e = next[e]) {
					int v = to[e];
					if (v == parent[u]) continue;
					parent[v] = u;
					pw[v] = w[e];
					children[u].add(v);
					st[top][0] = v; st[top][1] = 0; top++;
				}
			} else {
				post[postPtr++] = u;
			}
		}

		up = new long[n + 1];

		long lo = 0, hi = dia;
		while (lo < hi) {
			long mid = (lo + hi) >>> 1;
			if (feasible(mid)) hi = mid;
			else lo = mid + 1;
		}
		System.out.println(lo);
	}
}

题目内容

在一颗覆盖全国的光纤通信网络中， $n$ 条光纤节点按照道路连接形成一棵无向树。相邻节点之间的光纤长度记为 $w_e$ 。长距离信号衰减明显，为了提升整体质量，工程师计划在不改变节点位置的前提下，将网络切割成若干段，使得每一段内部的最远通信距离(即直径)都不超过某个值。

具体来说，工程师可以拆除至多 $k$ 条光纤(删除对应的边)，从而把原树分成至多 $k+1$ 个连通部分。定义一棵树(或连通部分)的 直径 为该部分中两点间最短路径的最大长度，即所有路径长度之 $max$ 。

请你计算：在最多拆除 $k$ 条光纤的前提下，所能得到的最小可能最大直径值。也就是说，你需要给出一个整数 $D$ ，满足：

• 经过不超过 $k$ 次拆除操作后，所有连通部分的直径 $≤ D^*$ ;

• 并且不存在更小的整数满足上述条件

【名词解释】

• 树：树是一种无向、连通且无环的图结构。

• 直径：对一棵树(连通部分)，其直径指树中两点间最短路径长度的最大值。

输入描述

第一行输入两个整数 $n$ 和 $k(2≤n≤2×10^5，0≤k≤n-1)$ ，分别表示网络的节点数量与最多可拆除的光纤数量。

接下来 $n-1$ 行，每行输入三个整数 $u_i,v_i,w_i(1≤ u_i,v_i≤n,u_i ≠ v_i,1≤w_i≤10^9)$ ，表示一条长度为 $w_i$ 的光纤连接节点 $u_i$ 与 $v_i$ 。

输入保证所有节点形成一棵树。

输出描述

输出一个整数，表示拆除不超过 $k$ 条光纤后，所有连通部分可能达到的最小最大直径。

样例1

输入

5 1
1 2 1
2 3 2
3 4 2
4 5 1

输出

3

说明

说明：若拆除边 $(3,4)$，两段子树分别包含节点 {$1,2,3$} 与 {$4,5$}，其直径分别为 $1+2=3$ 与 $1$ ，因此最大直径为 $3$ 且无法做到更小。

样例2

输入

7 2
1 2 5
2 3 4
2 4 3
4 5 2
4 6 2
6 7 1

输出

5