Cocoly1990's Blog

一道斜率优化的好题，别的题解也说得很清楚了，容斥一下单调队列维护凸壳一下就好了，但明显的斜率优化相对于下面的做法比较复杂。

首先考虑猜结论，显然手玩样例会发现最后都是一条链加上一条边构成一个环，我们设 $siz_x$ 是 $x$ 的子树大小，如果连接了 $u,v$，那么该路径上不同子树之间的点相互访问的简单路径增加了一条，那么答案增加了 $\sum\left(n-size\left[i\right]\right)\times size\left[i\right]$，$i$ 是该路径上的点。

显然要最小化 $\sum size\left[i\right]^2$，然后易证连接的点必然是叶子或根，否则使其再向子树扩展得到的 $\sum size\left[i\right]^2$ 更小。

那么根据λᴉʍ大佬的说法，我们用求直径的方法求两次就好了。关于为什么这么可以，我一时间也没有很好地证明。其实关于直径的方法我也是看了题解才知道，最开始的思路只停留在上面。如果希望正解的还是最好去写斜率优化，可以看出最后树的直径相较于斜率优化在运行时间上差很多。

贴个Code吧，Pre() 是关于子树的处理，dfs() 是答案的统计，存树用的是链式前向星

#include<bits/stdc++.h>
#define ll long long
#define vv (e[i].v)
#define Maxn 500007
inline int read(){
   register int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
   return s*w;
}
using namespace std ;
ll n , head[Maxn] , tot , ans[Maxn] , siz[Maxn] , u , v , Maxi ;
struct Edge
{
	int v , next ;
}e[Maxn << 1] ;
void add(int u , int v)
{
	e[++ tot].v = v ;
	e[tot].next = head[u] ;
	head[u] = tot ;
}
void Pre(int now , int last)
{
	siz[now] = 1 ;
	for(int i = head[now] ; i ;i = e[i].next)
	{
		if(vv == last) continue ;
		Pre(vv , now) ;
		siz[now] += siz[vv] ;
	}
}
void dfs(int now , int last)
{
	for(int i = head[now] ; i ;i = e[i].next)
	{
		if(vv == last) continue ;
		//Pre(vv , now) ;
		ans[vv] = ans[now] + (siz[now] - siz[vv]) * siz[vv] ;
		dfs(vv , now) ;
	}	
}
void MaxF()
{
	Maxi = 1 ;
	for(int i = 1 ; i <= n ; i ++) Maxi = (ans[Maxi] < ans[i]) ? i : Maxi ;
}
int main()
{
	n = read() ;
	for(int i = 1 ; i <= n - 1 ; i ++)
	{
		u = read() ; v = read() ;
		add(u , v) ;
		add(v , u) ;
	}
	Pre(1 , -1) ;
	ans[1] = n * (n - 1) / 2 ;
	dfs(1 , -1) ;
	MaxF() ;
	Pre(Maxi , 0) ;
	ans[Maxi] = ans[1] ;
	dfs(Maxi , 0) ;
	MaxF() ;
	cout << ans[Maxi] ;
	return 0 ; 
}