#P3617. 第3题-拆除光纤线路
          
                        
                                    
                      
        
              - 
          
          
                      1000ms
            
          
                      Tried: 16
            Accepted: 3
            Difficulty: 8
            
          
          
          
                       所属公司 : 
                              阿里
                                
            
                        
              时间 :2025年9月7日-阿里云
                              
                      
          
 
- 
                        算法标签>二分算法          
 
第3题-拆除光纤线路
思路
- 
二分答案:对 D 二分,检查是否能用不超过 k 次删边,使所有连通块直径 ≤D。
 - 
可行性检查(贪心 + 树形 DP,自底向上):
- 
固定根(任意如 1),一次性预处理父子关系与后序序列。
 - 
对每个节点,把每个子树向上“贡献”的路径长度记为 t=up[v]+w(u,v)。
- 若 t>D,该子边必须切断(计一次删除)。
 - 否则加入数组 A。
 
 - 
为保证以该节点为“拐点”的路径不超标,数组 A 中任意两条保留路径的和必须 ≤D。这等价于只需保证最大两条之和 ≤D。因此:
- 将 A 排序;当 ∣A∣≥2 且 A[−1]+A[−2]>D 时,不断删除最大的那条并计数(贪心最优)。
 - 该节点向父节点仅需保留一条“向上路径”,取当前最大者:up[u]=A[−1](若 A 为空则为 0)。
 
 
 - 
 - 
如此统计到根的总删除次数 cuts,判断 cuts≤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 条光纤节点按照道路连接形成一棵无向树。相邻节点之间的光纤长度记为 we 。长距离信号衰减明显,为了提升整体质量,工程师计划在不改变节点位置的前提下,将网络切割成若干段,使得每一段内部的最远通信距离(即直径)都不超过某个值。
具体来说,工程师可以拆除至多 k 条光纤(删除对应的边),从而把原树分成至多 k+1 个连通部分。定义一棵树(或连通部分)的 直径 为该部分中两点间最短路径的最大长度,即所有路径长度之 max 。
请你计算:在最多拆除 k 条光纤的前提下,所能得到的最小可能最大直径值。也就是说,你需要给出一个整数 D ,满足:
- 
经过不超过 k 次拆除操作后,所有连通部分的直径 ≤D∗ ;
 - 
并且不存在更小的整数满足上述条件
 
【名词解释】
- 
树:树是一种无向、连通且无环的图结构。
 - 
直径:对一棵树(连通部分),其直径指树中两点间最短路径长度的最大值。
 
输入描述
第一行输入两个整数 n 和 k(2≤n≤2×105,0≤k≤n−1) ,分别表示网络的节点数量与最多可拆除的光纤数量。
接下来 n−1 行,每行输入三个整数 ui,vi,wi(1≤ui,vi≤n,ui=vi,1≤wi≤109) ,表示一条长度为 wi 的光纤连接节点 ui 与 vi 。
输入保证所有节点形成一棵树。
输出描述
输出一个整数,表示拆除不超过 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