【题解】P7238「DCOI」迷失森林

\(1~\text{树的直径}\)

Subtask5 满足 \(n\le10^3\)，因此可以 \(O(n^2)\) 模拟建树。

以 \(u\) 为根的子树中，\(u\) 必选时树的直径为 \(d_1+d_2-1\)。

其中 \(d_1,d_2\) 分别表示以 \(u\) 为根最大、次大深度。

\(2~\text{森林直径}\)

引理：森林直径必由树的直径扩展而来。

证明：一条边 \((u,v)\) 若存在于树的直径中，必在森林中有一对应子树存在。

此时该对应子树对应的最长链一定是森林的最长链。

设 \(d_1[u],d_2[u]\) 分别表示以 \(u\) 为根最大、次大深度，\(d[u]\) 表示以 \(1\) 为根 \(u\) 的深度，\(v\) 是 \(u\) 的孩子。

考虑到以 \(u\) 为根子树的转移：

记 \(S(n)=\frac{n(n+1)}{2}\)，以 \(u\) 为根，森林直径必过 \(u\) 的答案：

最终森林直径：

#include<cstdio>
#include<vector>
typedef long long ll;
inline int in();
inline void wr(ll);
const int N=(int)1e6+5;
int d1[N],d2[N],d[N];
std::vector<int>G[N];
ll ans;
inline void dfs(int,int);
inline ll mx(ll,ll);
inline ll S(int);
int main(int argc,char**argv){
#ifndef ONLINE_JUDGE
	freopen("forest.in","r",stdin);
	freopen("forest.out","w",stdout);
#endif
	register int n=in();
	for(register int i=1;i<n;++i){
		register int u=in(),v=in();
		G[u].push_back(v),
		G[v].push_back(u);
	}
	dfs(1,1);
	wr(ans+d1[1]*2+1),putchar('\n');
}
inline void dfs(int u,int fa){
	for(register std::vector<int>::iterator it=G[u].begin();it!=G[u].end();++it){
		register int v=*it;
		if(v==fa)continue;
		d[v]=d[u]+1,dfs(v,u);
		if(d1[v]+1>d1[u])d2[u]=d1[u],d1[u]=d1[v]+1;
		else if(d1[v]+1>d2[u])d2[u]=d1[v]+1;
	}
	ans=mx(ans,S(d1[u])+S(d2[u])+d[u]*1ll*(d1[u]+d2[u]-2));
}
inline ll S(int n){
	return n*1ll*(n+1)/2;
}
inline ll mx(ll x,ll y){
	return x>y?x:y;
}
inline int in(){
	register char c=getchar();
	register int x=0,f=1;
	for(;c<'0'||c>'9';c=getchar())
		if(c=='-')f=-1;
	for(;c>='0'&&c<='9';c=getchar())
		x=(x<<1)+(x<<3)+(c&15);
	return x*f;
}
inline void wr(ll x){
	if(x<0)putchar('-'),x=-x;
	if(x/10)wr(x/10);
	putchar(x%10+'0');
}