功能型网站建设西安网站到首页排名

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

首先肯定二分

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

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

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

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

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

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

然后就完事了

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

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