本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-06-24 21:16:11

题意

设一棵树的权值为 $\max_{x}(\sum_i \left|w_i-x\right|)$，其中 $w_i$ 为所有边权，$x$ 取任意实数。给定 $n$ 个点 $m$ 条边的无向图，求其最大权值生成树。$n\le 2\times {10}^5,m\le 5\times {10}^5$。

题解

显然给定 $w$ 后取其中位数为 $x$ 一定最优。考虑枚举边权作为中位数 $x$，以其为分界点，认为 $w\le x$ 的边为白边，权值为 $x-w$；其余为黑边，权值为 $w-x$。此时若 $n$ 为奇数，则两种边各选 $\frac{n-1}2$ 条即可；若 $n$ 为偶数，考虑两种边各选 $\lfloor \frac{n-1}2\rfloor$ 条，即少选一条边，形成两个连通块。由于边权均非负，一定不会超过答案；而枚举到最终答案中位数时，会得到对应生成树去掉中位数边的两个连通块，而该边权值为 $0$，因此一定可以求出答案。

此时需要解决两种边分别选择 $c=\lfloor\frac{n-1}2\rfloor$ 条的最大生成森林，官解给了一种每次增加一条白边的做法，笔者不会证也没写。事实上目前题意即为 [国家集训队] Tree I，可以使用 wqs 二分求解。具体地，设 $f_i$ 表示 $i$ 条白边的答案，则 $(i,f_i)$ 形成了一个上凸包。证明不太会，感性理解可以从没有白边开始，每次增加一条白边，答案能增多的值不多于上次。从没有黑边开始同理，这两种各能得到四分之一个凸包，因此整体是上凸的。

考虑用斜率为 $k$ 的直线切这个凸包，切到的点 $t$ 随 $k$ 增大而减小。确定 $k$ 后要最大化截距 $b=f_i-ki$，可以将 $-ki$ 的贡献放到每条白边上，即将白边权值改为 $x-w-k$，然后用 Kruskal 求最大生成森林，从而得到最大的 $b$ 和对应的白边条数 $t$。这里可在 $b$ 最大前提下要求白边数量 $t$ 尽可能少，然后二分出 $t\le c$ 的最大 $k$，该 $k$ 即可切到 $(f_c,c)$ 点，再跑一遍后求 $f_c=b+kc$ 即为答案。对所有中位数取最大值即可，注意要判掉无解情况，时间复杂度 $O(m^2\log V\lpha(n))$，可以得到 $50$ 分。

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1e5+10;
const int P=1e9+1e7;
const ll inf=1e18+1e17;
int n,m,ct,c,a[N],f[N],s[N]; ll res,ans=-inf;
struct edg{int u,v,w,f;}e[N],E[N];
bool cmp(edg ta,edg tb)
{
	if(ta.w==tb.w) return ta.f<tb.f;
	return ta.w>tb.w;
}
int finds(int x) {return f[x]==x?x:f[x]=finds(f[x]);}
bool merg(int x,int y)
{
	x=finds(x),y=finds(y);
	if(x==y) return false;
	s[y]+=s[x],f[x]=y; return true;
}
int chk(int x,int k)
{
	for(int i=1;i<=m;i++) e[i]=E[i],e[i].f=(e[i].w<=x),e[i].w=abs(e[i].w-x)-e[i].f*k;
	sort(e+1,e+1+m,cmp),res=0; int C=0,cx=0;
	for(int i=1;i<=n;i++) f[i]=i,s[i]=1;
	for(int i=1;i<=m;i++)
	{
		if(merg(e[i].u,e[i].v)) C++,cx+=e[i].f,res+=e[i].w;
		if(C==c*2) break;
	}
	return cx;
}
ll check(int x)
{
	int l=-P,r=P,rk=P+1;
	while(l<=r)
	{
		int mid=((l+r)>>1),t=chk(x,mid);
		if(t<=c) rk=mid,r=mid-1;
		else l=mid+1;
	}
	if(rk==P+1||chk(x,rk-1)<c) return -inf;
	chk(x,rk); return res+1ll*c*rk;
}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m,c=((n-1)>>1);
	for(int i=1;i<=m;i++) cin>>E[i].u>>E[i].v>>E[i].w,a[i]=E[i].w;
	sort(a+1,a+1+m),ct=unique(a+1,a+1+m)-a-1;
	for(int i=1;i<=ct;i++) ans=max(ans,check(a[i]));
	cout<<ans;
	return 0;
}

观察上述代码，注意到同时给所有边加上一个值 $x$ 不会改变最终树的形态，即求出的白边条数 $t$ 不变。因此白边边权变为 $2x-k-w$，黑边边权变为 $w$。此时 chk 函数的结果只与 $X=2x-k$ 有关，根据上面的凸性可以说明此时 $t$ 随 $X$ 增大而增大，因此可以直接二分 $X$ 求解。

此时要求的问题如下：原图中每条边产生白边 $(u,v,X-w)$ 和黑边 $(u,v,w)$，求 $w\le x$ 的白边和 $w>x$ 的黑边形成的 $2c$ 条边的最大生成森林。考虑直接在 $2m$ 条边中用 Kruskal 求解，并证明这样做是对的。首先若存在黑边 $w_1$ 和白边 $X-w_2$，且 $w_1<w_2$，显然改为黑边 $w_2$ 和 白边 $X-w_1$ 更优，因此跑出的结果一定是 $w$ 上某个前缀为白边，之后为黑边。

此时显然存在一个 $x$ 满足该前缀 $w\le x$ 且之后 $w>x$，因此这样做是对的。最终答案为 $\sum\left|x-w\right|$，在黑白边均为 $c$ 条时即为 $\sum_{i>x} w_i-\sum_{i\le x}w_i$，即跑出的最大生成森林权值和减去 $cX$，这样就做完了。由于按 $X-w$ 排序只需要将 $w$ 有序的序列翻转，不需要每次 chk 都排序，时间复杂度为 $O(m\log V\lpha(n))$。

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int N=5e5+10;
const int P=1e9+1e7;
const ll inf=1e18+1e17;
int n,m,k,c,a[N],f[N],s[N],C,cx; ll res,ans=-inf;
struct edg{int u,v,w;}e[N],E[N];
bool cmp(edg ta,edg tb) {return ta.w>tb.w;}
int finds(int x) {return f[x]==x?x:f[x]=finds(f[x]);}
bool merg(int x,int y)
{
	x=finds(x),y=finds(y);
	if(x==y) return false;
	s[y]+=s[x],f[x]=y; return true;
}
void add(edg te,bool f)
{
	if(C==c*2) return;
	if(merg(te.u,te.v)) C++,cx+=f,res+=te.w;
}
void chk(ll X)
{
	for(int i=1;i<=m;i++) e[i]=E[m-i+1],e[i].w=X-e[i].w;
	res=0,C=0,cx=0; int pa=1,pb=1;
	for(int i=1;i<=n;i++) f[i]=i,s[i]=1;
	while(pa<=m&&pb<=m)
	{
		if(e[pa].w>E[pb].w) add(e[pa],1),pa++;
		else add(E[pb],0),pb++;
	}
	while(pa<=m) add(e[pa],1),pa++;
	while(pb<=m) add(E[pb],0),pb++;
}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m,c=((n-1)>>1);
	for(int i=1;i<=m;i++) cin>>E[i].u>>E[i].v>>E[i].w;
	sort(E+1,E+1+m,cmp);
	ll l=-P,r=2*P,rk=-P-1;
	while(l<=r)
	{
		ll mid=((l+r)>>1); chk(mid);
		if(cx<=c) rk=mid,l=mid+1;
		else r=mid-1;
	}
	chk(rk),cout<<res-c*rk;
	return 0;
}