CF1218A

虚高 *2800。放模拟赛 T2 人均切了。

先想树的情况怎么做。枚举每个起点，剩下的贡献就是定值。求这个值可以钦定 $1$ 为根求出所有的 $siz$，然后枚举 $i$ 为起点，以 $i$ 为起点的答案就是 $\sum siz_i$ 加上 $i$ 到 $1$ 路径上，不含 $1$ 的所有点的 $\sum_j n-2\times siz_j$。

然后放到基环树上，发现需要注意环的情况，在一个环上先往一个方向走和另一个方向的贡献是不一样的。发现可以通过一个环上的区间 dp 解决。

对于环上一个点 $i$ 的贡献，我们只考虑一个在环上，且不在起点所对应环上的点且不为 $i$ 的点 $j$，当染黑 $j$ 时，$i$ 造成的贡献。

设环上点编号为 $0,1,\cdots ,k-1$，对应点分别为 $a_0,a_1,\cdots,a_{k-1}$,$dp_{i,j}$ 为环上编号为 $i$ 的点开始的一段长为 $j$ 的区间的最大贡献，则有 $dp_{i,j}=\max(dp_{i,j-1}+(j-2)\times siz_{a_{i+j-1}},dp_{(i+1)\bmod k,j-1}+(j-2)\times siz_{a_i})$。其中 $siz$ 是将在环上的点视为根的 $siz$。

初始值 $dp_{i,1}$ 可以根据上面计算树的方法，得到以 $i$ 为根的子树内每个点为起点的答案，再取 $\max$。

发现空间会炸，于是滚动一下。能过。$O(n^2)$。

code：

int n,m;
int tot,head[N];
struct node{int to,nxt;}e[N<<1];
il void add(int u,int v){e[++tot]={v,head[u]},head[u]=tot;}
namespace s1{
	int siz[N],fa[N];
	void dfs1(int u,int f){
		siz[u]=1,fa[u]=f;
		go(i,u){
			int v=e[i].to;
			if(v==f)continue;
			dfs1(v,u),siz[u]+=siz[v];
		}
	}
	void solve(){
		dfs1(1,0);
		int sum=0;
		rep(i,1,n)sum+=siz[i];
		int ans=0;
		rep(i,1,n){
			int x=sum,u=i;
			while(u!=1)x+=n-2*siz[u],u=fa[u];
			ans=max(ans,x);
		}
		printf("%d\n",ans);
	}
}
namespace s2{
	int k,cyc,siz[N],dep[N],fa[N],dp[N][2],id[N];
	bool vis[N],inc[N];
	vector<int> g;
	void dfs1(int u,int f){
		vis[u]=1,dep[u]=dep[f]+1,fa[u]=f;
		go(i,u){
			int v=e[i].to;
			if(vis[v]){
				if(v!=f)cyc=(i+1)/2;
				continue;
			}
			dfs1(v,u);
		}
	}
	void find_cyc(int u,int v){
		vector<int> h;
		if(dep[u]<dep[v])swap(u,v);
		while(dep[u]>dep[v])g.eb(u),u=fa[u];
		while(u!=v)g.eb(u),h.eb(v),u=fa[u],v=fa[v];
		g.eb(u);
		while(h.size())g.eb(h.back()),h.pop_back();
	}
	void dfs2(int u,int f){
		siz[u]=1,fa[u]=f;
		go(i,u){
			int v=e[i].to;
			if(v==f||inc[v])continue;
			dfs2(v,u),siz[u]+=siz[v];
		}
	}
	void solve(){
		dfs1(1,0),find_cyc(e[cyc*2-1].to,e[cyc*2].to);
		for(int i=0;i<(int)g.size();i++)inc[g[i]]=1,id[g[i]]=i;
		for(int i:g)dfs2(i,0);
		k=g.size();int sum=0;
		rep(i,1,n)sum+=siz[i];
		rep(i,1,n){
			int x=sum,u=i;
			while(!inc[u])x+=n-2*siz[u],u=fa[u];
			dp[id[u]][1]=max(dp[id[u]][1],x+n-siz[u]);
		}
		rep(len,2,k){
			int p=len&1;
			rep(i,0,k-1)dp[i][p]=0;
			rep(i,0,k-1){
				int j=(i+len-1)%k;
				dp[i][p]=max(dp[i][p^1]+siz[g[j]]*(len-2),dp[(i+1)%k][p^1]+siz[g[i]]*(len-2));
			}
		}
		int ans=0;
		rep(i,0,k-1)ans=max(ans,dp[i][k&1]);
		printf("%d\n",ans);
	}
}
void Yorushika(){
	scanf("%d",&n);
	rep(i,1,n){
		int u=read()+1,v=read()+1;
		add(u,v),add(v,u);
	}
	s2::solve();
}
signed main(){
	int t=1;
	//	scanf("%d",&t);
	while(t--)
		Yorushika();
}