自动搬运

查看原文

来自洛谷，原作者为

	ANIG ̴̴̴̳̦̗̤̳̟̭̫̲̳̦̗̤̳̟̭̫̲̳̦̗̤̳̟̭̫̲̍̄̆̑͑͑̈̅͐̔̊̍̄̆̑͑͑̈̅͐̔̊̍̄̆̑͑͑̈̅͐̔̊̚̚̚阿尼哥，啊你个，又糖又扔

搬运于2025-08-24 23:11:33，当前版本为作者最后更新于2025-03-28 07:26:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

传送门

考虑树的情况。

首先问题可以转化成找到一条路径，把这条路径染成单调递增，其余点染成距离最近的路径上的点。

要求不同颜色点对最小，就是要求同色连通块大小平方和最大。

假如我们钦定了一个端点，则另一个端点是可以简单 dp 求出来的。

又可以发现，要找的路径的端点一定是叶子。

感受一下，是不是有点类似树的直径？那么我们大胆假设使用求树的直径的方法做这个题也是可以的。

于是我们考虑二次 dfs，先随便钦定一个端点，找到最优的另一个端点 $x$，再找到以 $x$ 为端点最优的 $y$，则此时 $(x,y)$ 就是我们要找的路径。

实际测试后可以发现这么做是对的。

非树的情况也是简单的。可以发现环上的颜色都相等，于是给边双缩点，转化成树上带权问题，直接套树的做法即可。

复杂度 $O(n)$。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e6+5,inf=1e18;
int n,m,siz[N],mk[N],f[N],g[N],dfn[N],low[N],idx=1,cnt,bh[N],sz[N];
vector<int>p[N],st;
vector<pair<int,int> >e[N];
void tarjan(int x,int y=0){
	dfn[x]=low[x]=++idx;
	st.push_back(x);
	for(auto [c,bh]:e[x]){
		if(!dfn[c]){
			tarjan(c,bh);
			low[x]=min(low[x],low[c]);
		}else if(bh!=(y^1))low[x]=min(low[x],dfn[c]);
	}
	if(dfn[x]==low[x]){
		int t;cnt++;
		do{
			t=st.back();
			st.pop_back();
			bh[t]=cnt;
			sz[cnt]++;
		}while(t!=x);
	}
}
void init(int x){
	mk[x]=1;siz[x]=sz[x];
	for(auto c:p[x]){
		if(mk[c])continue;
		init(c);
		siz[x]+=siz[c];
	}
	mk[x]=0;
}
void dfs(int x){
	mk[x]=1;
	for(auto c:p[x]){
		if(mk[c])continue;
		f[c]=f[x]+(siz[x]-siz[c])*(siz[x]-siz[c]);
		dfs(c);
	}
	g[x]=f[x]+siz[x]*siz[x];
	mk[x]=0;
}
int max_diversity(signed nn, signed mm,vector<signed> U,vector<signed> V){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	n=nn;m=mm;
	for(int i=1;i<=m;i++){
		int x=U[i-1],y=V[i-1];
		x++;y++;
		e[x].push_back({y,++idx});
		e[y].push_back({x,++idx});
	}
	idx=0;
	tarjan(1);
	for(int i=1;i<=n;i++){
		for(auto [c,bhs]:e[i]){
			if(bh[i]!=bh[c]){
				p[bh[i]].push_back(bh[c]);
			}
		}
	}
	init(1);
	dfs(1);
	int nw=1;
	for(int i=1;i<=cnt;i++){
		if(g[i]<g[nw])nw=i;
	}
	memset(f,0,sizeof(f));
	memset(g,0,sizeof(g));
	init(nw);
	dfs(nw);
	int res=inf;
	for(int i=1;i<=cnt;i++)res=min(res,g[i]);
	return (n*n-res)/2;
}