与树上边权、连通块、二分块相关的问题（抓住各连通块之间的联系，考虑增量）：CF444E

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133138502

https://www.luogu.com.cn/problem/CF444E

首先肯定二分

然后是棵树，所以考虑按顺序枚举边权

然后肯定会有连通块和并查集

考虑现在场上有多个连通块，我们只保留大于 midmid 的边

则每个连通块都必须往外连边

一个很朴素的思路是判定每个连通块外面是否够 ∑xi>w\sum x_i>w ，看起来是错的，但其实是对的

考虑其代价和贡献，因为有 xi≥1x_i\ge 1 ，所以当他在外面取 ww 走时，至少会放回 ww 进去，满足 ∑xi\sum x_i 不减

然后就完事了

然后你可以发现按顺序枚举边，判断啥时候不合法，甚至不需要二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include<bits/stdc++.h>
using namespace std;
//#define int long long 
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 3010
//#define M
//#define mo
struct node {
	int u, v, w; 
}a[N];
int n, m, i, j, k, T, u, v, w[N], val[N], f[N], sum;

int fa(int x) {
	if(f[x]==x) return x; return f[x]=fa(f[x]); 
}

signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	T=read();
//	while(T--) {
//
//	}
	n=read(); 
	for(i=1; i<n; ++i) a[i].u=read(), a[i].v=read(), a[i].w=read(); 
	for(i=1; i<=n; ++i) f[i]=i, val[i]=read(), w[i]=1, sum+=val[i]; 
	sort(a+1, a+n, [] (node x, node y) { return x.w<y.w; }); 
	for(i=1; i<n; ++i) {
		u=fa(a[i].u); v=fa(a[i].v); 
		f[u]=v; w[v]+=w[u]; val[v]+=val[u]; 
		if(w[v]>sum-val[v]) return printf("%lld", a[i].w), 0; 
	}
	printf("%d", a[n-1].w); 
	return 0;
}