题解 [CF1578L] Labyrinth

传送门

第一思路是二分+类树形DP
首先可以贪心从大到小加边+dsu将原图变为一棵树（其实这就是最大生成树但我没有意识到）
然后发现一定存在一种最优策略使得边权最小的边只被经过一次
于是可以从最小的这条边断开分治
但从一个连通块里找边权最小的边的复杂度炸了

于是正解是kruskal重构树，并且不用二分
发现刚才的复杂度瓶颈是找连通块内最小边
在重构树上这个最小边就是对应子树的根节点
于是树形DP即可

• 连通块内最大/小边权可以转化到kruskal重构树上处理，尤其适合需要从最大/小边划分开进行分治的情况

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 400010
#define ll long long
#define fir first
#define sec second
#define make make_pair
//#define int long long

char buf[1<<21], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
inline int read() {
	int ans=0, f=1; char c=getchar();
	while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
	while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
	return ans*f;
}

int n, m;
int dsu[N], ls[N], rs[N], tot;
ll c[N], val[N], sum[N], f[N];
int head[N], size;
struct tpl{int s, t, val;}t[N];
inline bool operator < (tpl a, tpl b) {return a.val>b.val;}
inline int find(int p) {return dsu[p]==p?p:dsu[p]=find(dsu[p]);}

void kruskal() {
	tot=n;
	for (int i=1; i<N; ++i) dsu[i]=i;
	sort(t+1, t+m+1);
	for (int i=1,f1,f2; i<=m; ++i) if ((f1=find(t[i].s))!=(f2=find(t[i].t))) {
		val[++tot]=t[i].val;
		dsu[f1]=dsu[f2]=tot;
		ls[tot]=f1, rs[tot]=f2;
	}
}

void dfs(int u) {
	// cout<<"dfs: "<<u<<endl;
	if (!ls[u]||!rs[u]) {sum[u]=c[u]; f[u]=INF; return ;}
	dfs(ls[u]); dfs(rs[u]);
	sum[u]=sum[ls[u]]+sum[rs[u]];
	f[u]=max(min(f[rs[u]]-sum[ls[u]], val[u]-sum[ls[u]]), min(f[ls[u]]-sum[rs[u]], val[u]-sum[rs[u]]));
}

signed main()
{
	n=read(); m=read();
	for (int i=1; i<=n; ++i) c[i]=read();
	for (int i=1,u,v,w; i<=m; ++i) {t[i].s=read(); t[i].t=read(); t[i].val=read();}
	kruskal();
	dfs(tot);
	printf("%lld\n", f[tot]>0?f[tot]:-1);

	return 0;
}