cf444E. DZY Loves Planting(并查集)

题意

题目链接

sol

神仙题啊orzzzzzz

考场上的时候直接把树扔了对着式子想，想1h都没得到啥有用的结论。

然后cf正解居然是网络流？？出给noip模拟赛t1？？？￥%……&（（……%&（（

说一下非网络流解法吧。

首先题目中给出的\(g(i, p_i)\)我们可以认为是对于每个节点\(i\)，分配一个节点\(p_i\)，同时还有数量\(x_i\)的限制

同时题目中要求的是最小值最大，不难想到二分答案。但其实只要把边从小到大排序，依次考虑每条边能否成为答案就行了

用并查集维护节点之间的联通性，对于一条边来说，如果这条边可以成为答案，那么对于当前已经合并的每个点，我们都需要给它分配一个未被合并的点(注意这里边权是已经排好序的)

维护\(siz[x]\)表示\(x\)节点的连通块的大小，\(sum = \sum_{i = 1}^n x_i\), \(f[x]\)表示已经合并的节点的\(x_i\)之和(也就是不能使用的点)

那么一条边可以被合并的条件为\(siz[x] <= sum - f[x]\)

#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;
}