题解 [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;
}
你可能想看：