吉吉王国

题目描述：
链接：https://ac.nowcoder.com/acm/problem/210473
来源：牛客网

吉吉王国有nn个城市，其中11号城市就是吉吉王国的首都，并且吉吉王国有n-1n−1条道路，每条道路都有一个长度dd，你可以从任意一点uu到达任意一点vv。但是最近吉吉***生了***，除了首都外，每个只有一条道路连向的城市出现了反叛军。

这些城市的反叛军开始向吉吉王国的首都发起了进攻，如果让他们到达首都，那么吉吉国王就要换人了。吉吉国王现在需要快速切断一些道路，使得没有一个城市的反叛军可以到达首都。但是由于物资的限制，他能切断的道路的总长度和不能超过mm，并且要保证切断道路尽量快，因此切断的道路中最长的长度要尽可能小。

现在赶紧告诉吉吉国王切断的道路的最长长度在最小的时候是多少吧。

吐槽解释：
很坑一道题目，题目说的是要找到最长边最短的方案，而不是总权值最小的方案，这让前几发一直维护总权值最小，结果通过55%的我情何以堪。
于是题目要求就变成了，求剪掉所有叶子节点且总权值不超过m的方案中，最长边最短的值。
还好有大佬代码捞我一手····
dp数组开两个维度dp[x][y]，表示假定最长边为y的时候，剪掉x的孩子的所有叶子节点的最小总权值。
然后还当成一维处理就好，毕竟y不同的dp值不会相互影响，只需要加一个for循环同时维护y次就好了。
for(枚举最长边长度k 0~N )
dp[x][k]+=min(EdgeValue_from_x_to_son,dp[son][k]) //小心爆inf 记得特判
//以及，如果自己的k比直接剪断孩子的边权小，那就不能这样做
剩下的看代码就ok
再说优化，这题还可以二分枚举最长边，然后跑log次。

顺带一提，这题数据还是有点弱，直接维护总权值最小方案是否合法，然后输出最长边的最小值也能过，就比如
这组数据：
4 10
1 2 10
2 3 5
2 4 6
只有剪掉2孩子的一种合法方案，正解输出10。
但是有的输出6的解也能过

//代码原地址  作者：Aaaa🎈aaaA 
//https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44643900
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e3 + 10, M = N * 2;
static const int INF = 0x3f3f3f3f;
int h[N], e[M], ne[M], w[M], idx;
int n, m;
int f[N][N];//f[x][y] 切断x的孩子，假定最长边为y时的权值和
/*
坑点在于这个题目求的是总边权不超过m的所有方案中，
最长边最小的值
看一下这两组数据
4 10
1 2 10
2 3 5
2 4 6
结果应该是10

4 11
1 2 10
2 3 5
2 4 6
结果应该是6

其实直接开一维，然后枚举最长边，跑N次也是可以的
这里直接开二维，第二维度之间互不干扰
优化的话个人感觉可以考虑二分最长边
然后跑log次dfs，如果某条边长度大于我们设置的上界，直接设为inf
*/

void add(int a, int b, int c) {
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx++;
}

void dfs(int u, int father) {
    bool is_leaf = true;
    for (int i = h[u]; i != -1; i = ne[i]) {//自己不是叶子
        int j = e[i], c = w[i];
        if (father == j) continue;
        is_leaf = false;
        dfs(j, u);//儿子节点j 直接切断自己和这个孩子的边权重c
        for (int k = 0; k < c; ++k) {//假定子节点最长边小于c时，不能剪掉自己跟孩子的边
            if (f[j][k] < INF)
                f[u][k] += f[j][k];
            else
                 f[u][k] = INF;
        }
        for (int k = c; k < N; ++k) {//假定子节点最长边大于等于c时，可以剪掉自己跟孩子的边
            f[u][k] += min(c,f[j][k]);
        }
    }
    if (is_leaf) {//如果自己是叶子节点 没有孩子 赋值inf
        for (int k = 0; k < N; ++k) {
            f[u][k] = INF;
        }
    }
}

void solve() {
    memset(h, -1, sizeof(h));
    cin >> n >> m;
    for (int i = 1; i < n; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);//建图
    }
    dfs(1, -1);
    int ans = -1;
    for (int i = 0; i < N; ++i) {
        if (f[1][i] <= m) {
            ans = i;
            break;
        }
    }
    cout << ans << endl;
}

int main() {
#ifdef HelpIN
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}