cf444E. DZY Loves Planting(并查集)

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, fa[MAXN], x[MAXN], siz[MAXN], sum;
struct Edge {
    int u, v, w;
    bool operator < (const Edge &rhs) const {
        return w < rhs.w;
    }
}E[MAXN];
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int main() {
    N = read();
    for(int i = 1; i <= N; i++) fa[i] = i, siz[i] = 1;
    for(int i = 1; i <= N - 1; i++) E[i].u = read(), E[i].v = read(), E[i].w = read();
    sort(E + 1, E + N);
    for(int i = 1; i <= N; i++) x[i] = read(), sum += x[i];
    for(int i = 1; i <= N - 1; i++) {
        int fx = find(E[i].u), fy = find(E[i].v);
        if(fx == fy) continue;
        fa[fy] = fx; siz[fx] += siz[fy]; x[fx] += x[fy];
        if(siz[fx] > sum - x[fx]) {printf("%d\n", E[i].w); return 0;}
    }
    printf("%d\n", E[N - 1].w);
    return 0;
}