题目链接：https://ac.nowcoder.com/acm/contest/6234/H
题目大意：有一棵n节点的树，每个节点上有权值，希望你把他的k-1条边拆开。形成k棵子树，每棵树的权值为节点权值的和。问这k棵子树的最大权值最小为多少？

思路：二分，然后我们思考，对于一个节点，他会和若干子节点连接，并且可能和祖先节点连接
图片说明
思路：先二分一下，这个最小值。然后在树上能不能分成为<=k棵子树。我们怎么贪心的分树：
对这个树，我们先处理2,5,6,7。一定是2和若干的子节点在一起，那么其他的每个子节点都会形成一颗树。我们希望2上连接的子节点越多越好并且权力和<=mid。那么对5, 6, 7的权值排序。一直加直到>mid。就不能加，那么其他的每个节点形成一颗子树。对于2连接的子树的权值和。应该作为2的权值。用于1的贪心。对3，4子树处理完后：
图片说明
对1的贪心思路和2的贪心思路一样。

时间复杂度：O(nlogn)：因为每个节点只会排序一次。

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

vector<vector<LL> > v(100005);
vector<LL> g[100005];
LL w[100005], ANS=0;

LL DFS(LL u, LL fa, LL x){
    LL s=w[u];
    for(auto to: v[u]){
        if(to==fa) continue;
        g[u].push_back(DFS(to, u, x));
    }
    sort(g[u].begin(), g[u].end());
    for(int i=0; i<g[u].size(); i++){
        if(s+g[u][i]>x){
            ANS+=g[u].size()-i;
            break;
        }
        else{
            s+=g[u][i];
        }
    }
    g[u].clear();
    return s;
}

bool check(LL x, LL k){
    ANS=1;
    DFS(1, 0, x);
    return ANS<=k;
}

int main(){

    int T, cas=1, x; scanf("%d", &T);
    while(T--){
        LL n, k, x, y; scanf("%lld%lld", &n, &k);
        for(int i=1; i<n; i++){
            scanf("%lld%lld", &x, &y);
            v[x].push_back(y);
            v[y].push_back(x);
        }
        LL l=0, r=0, ans=0;
        for(int i=1; i<=n; i++){
            scanf("%lld", &w[i]);
            l=max(l, w[i]); r+=w[i];
        }
        while(l<=r){
            LL mid=l+r>>1;
            if(check(mid, k)){
                r=mid-1, ans=mid;
            }
            else{
                l=mid+1;
            }
        }
        for(int i=1; i<=n; i++){
            v[i].clear();
        }
        printf("Case #%d: %lld\n", cas++, ans);
    }

    return 0;
}