【题意】：给出一棵树，根节点为1，每条边有一个代价。要求切去其所有的叶子节点，且总代价不能超过m，问切去的边中的最大的边最小是多少。 【题解】：最大值最小问题，基本上就是二分答案+判定。
这题的判定需要用到树dp。
设状态dp[u]为以u为根的子树切去其下方叶子节点的最少代价。
非叶子节点：
dp[u] += min(dp[v], w(u, v)), v 为 u 儿子。
叶子节点：
dp[u] = inf;
最后判断dp[1]与m的关系就可以了。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define mp make_pair
15 #define fi first
16 #define se second
17 #define lc(x) (x << 1)
18 #define rc(x) (x << 1 | 1)
19 #define lowbit(x) (x & (-x))
20 #define ll long long
21 #define maxn 1010
22 const int inf = 1 << 20;
23 int n, m, limit;
24 int dp[maxn];
25 struct Edge {
26 int v, w;
27 Edge(){}
28 Edge(int _v, int _w) {
29 v = _v, w = _w;
30 }
31 };
32 vector<Edge> vec[maxn];
33
34 void dfs(int u, int fa) {
35 dp[u] = 0;
36 int size = vec[u].size();
37 for(int i = 0; i < size; i++) {
38 int v = vec[u][i].v, w = vec[u][i].w;
39 if(v == fa) continue;
40 if(w > limit) w = inf;
41 dfs(v, u);
42 dp[u] += min(dp[v], w);
43 }
44 if(!dp[u]) dp[u] = inf;
45 }
46
47 void solve() {
48 int ans = -1;
49 int l = 1, r = 1000;
50 while(l <= r) {
51 int mid = (l + r) >> 1;
52 limit = mid;
53 dfs(1, -1);
54 if(dp[1] <= m) ans = mid, r = mid - 1;
55 else l = mid + 1;
56 }
57 cout << ans << endl;
58 }
59
60 int main() {
61 while(~scanf("%d%d", &n, &m)) {
62 if(!n) break;
63 for(int i = 1; i <= n; i++) vec[i].clear();
64 for(int i = 1; i < n; i++) {
65 int u, v, w;
66 scanf("%d%d%d", &u, &v, &w);
67 vec[u].pb(Edge(v, w));
68 vec[v].pb(Edge(u, w));
69 }
70 solve();
71 }
72 return 0;
73 }
74