自动搬运

查看原文

来自洛谷，原作者为

	3493441984zz **

搬运于2025-08-24 21:50:33，当前版本为作者最后更新于2019-01-15 14:01:49，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

小声$bb$：

居然没有题解。。赶紧水一波

调了我半天。。结果$if$里$==$写成了$=qwq$

---

回到正题：

对于最大值，我们把一棵树拆开后，把两棵树的直径的两端连起来就可以了

对于最小值，我们把一棵树拆开后，把两棵树的直径中点相连就可以了

（说的轻巧）

那就详细的讲讲怎么求吧

---

变量声明：

$dep[i]$：$i$节点的深度

$f[i]$：以$i$为根的子树的最长直径

$d[i][j](j\in\{0,1,2\})$:分别表示从$i$节点向下的最长链，次长链，和次次长链$qwq$

$w[i][j](j\in\{0,1\})$：分别表示以$i$节点的子节点为根的子树中最长直径和次长直径

$lian[i]$：表示$i$节点出发能走的最长长度，也就是可能会往上面走，其实就是把当前节点当做根节点的最长链长度

$fa[i]$：存的父亲及节点

$g[i]$：表示删除$i$点与$fa[i]$点之间的边后，以$1$为根的那棵树的最长直径

$head[i],edge[i]$：普通前向星

---

实现:

首先，我们用一次$dfs$求出$f,fa,d,w,dep$数组，详细过程在代码中注释了：

void Dfs1(int u)
{
	for(int i=head[u];i;i=edge[i].nxt)
	{
		int v=edge[i].to;
		if(v==fa[u])//不是父亲 
			continue;
		dep[v]=dep[u]+1;//更新深度 
		fa[v]=u;//更新父亲节点 
		Dfs1(v);//递归 
		f[u]=max(f[u],f[v]);//更新以u根的子树最大直径，初始值为子树的最大直径 
		int tmp=d[v][0]+1;
		if(tmp>d[u][0])//更新d数组 
		{
			d[u][2]=d[u][1];
			d[u][1]=d[u][0];
			d[u][0]=tmp;
		}
		else
			if(tmp>d[u][1])
			{
				d[u][2]=d[u][1];
				d[u][1]=tmp;
			}
			else
				if(tmp>d[u][2])
					d[u][2]=tmp;
		tmp=f[v];
		if(tmp>w[u][0])//更新w数组 
		{
			w[u][1]=w[u][0];
			w[u][0]=tmp;
		}
		else
			if(tmp>w[u][1])
				w[u][1]=tmp;
	}
	f[u]=max(f[u],d[u][0]+d[u][1]);//更新直径 
}

那么处理出这些后，我们就要开始拆边了，我们假设当前节点为$u$，那么我们枚举子节点$v$，那么拆了这条边后，就更新$g$数组，这时侯有$3$种情况：

先再贴一下$g$的定义：删除$i$点与$fa[i]$点之间的边后，以$1$为根的那棵树的最长直径~~（我不是在水字数）~~

$1$、删除的$v$点在$u$点的最长链$d[u][0]$上

那么以$1$为根的子树的直径可能会是$u$这个点的次长链$d[u][1]$与次次长链$d[u][2]$相加的，或者是当前点$u$向上走最长的路$lian[u]$与次长链$d[u][1]$相加组成直径

代码：

if(tmp==d[u][0])
{
	g[v]=max(max(g[v],d[u][1]+d[u][2]),lian[u]+d[u][1]);
	lian[v]=max(lian[v],d[u][1]+1);//顺便更新
}

$2$、删除的$v$点在$u$点的次长链$d[u][1]$上

那么以$1$为根的子树的直径可能会是$u$这个点的最长链$d[u][0]$与次次长链$d[u][2]$相加的，或者是当前点$u$向上走最长的路$lian[u]$与最长链$d[u][0]$相加组成直径

代码：

if(tmp==d[u][1])
{
	g[v]=max(max(g[v],d[u][0]+d[u][2]),lian[u]+d[u][0]);
	lian[v]=max(lian[v],d[u][0]+1);//顺便更新
}

$3$、删除的$v$点在$u$点的次次长链$d[u][2]$上

那么以$1$为根的子树的直径可能会是$u$这个点的最长链$d[u][0]$与次长链$d[u][1]$相加的，或者是当前点$u$向上走最长的路$lian[u]$与最长链$d[u][0]$相加组成直径

代码：

if(tmp==d[u][2])
{
	g[v]=max(max(g[v],d[u][0]+d[u][1]),lian[u]+d[u][0]);
	lian[v]=max(lian[v],d[u][0]+1);//顺便更新
}

但是仅仅考虑上述情况还不够，以$1$为根的子树的直径不一定会经过$u$点，所以还要与它子节点为根的子树的直径取最大值

代码：

tmp=f[v];
if(tmp==w[u][0])
	g[v]=max(g[v],w[u][1]);
else
	g[v]=max(g[v],w[u][0]);

那么当我们删除$u,v$之间的边后，把两端相连就是最长直径，也就是

if(ansmax<g[u]+f[u]+1)
{
	ansmax=g[u]+f[u]+1;
	maxx=fa[u],maxy=u;
}

而最小值就是两个直径中点相连，也就是

int tmp=max(max(f[u],g[u]),(f[u]+1)/2+(g[u]+1)/2+1);
if(ansmin>tmp)
{
	ansmin=tmp;
	minx=fa[u],miny=u;
}

自然第二次$dfs$可以直接搞出来

代码：

void Dfs2(int u)
{
	if(u!=1)
	{
		if(ansmax<g[u]+f[u]+1)
		{
			ansmax=g[u]+f[u]+1;
			maxx=fa[u],maxy=u;
		}
		int tmp=max(max(f[u],g[u]),(f[u]+1)/2+(g[u]+1)/2+1);
		if(ansmin>tmp)
		{
			ansmin=tmp;
			minx=fa[u],miny=u;
		}
	}
	for(int i=head[u];i;i=edge[i].nxt)
	{
		int v=edge[i].to;
		if(v==fa[u])
			continue;
		lian[v]=max(lian[v],lian[u]+1);
		g[v]=max(g[v],g[u]);
		int tmp=d[v][0]+1;
		if(tmp==d[u][0])
		{
			g[v]=max(max(g[v],d[u][1]+d[u][2]),lian[u]+d[u][1]);
			lian[v]=max(lian[v],d[u][1]+1);
		}
		else
			if(tmp==d[u][1])
			{
				g[v]=max(max(g[v],d[u][0]+d[u][2]),lian[u]+d[u][0]);
				lian[v]=max(lian[v],d[u][0]+1);
			}
			else
			{
				g[v]=max(max(g[v],d[u][0]+d[u][1]),lian[u]+d[u][0]);
				lian[v]=max(lian[v],d[u][0]+1);
			}
		tmp=f[v];
		if(tmp==w[u][0])
			g[v]=max(g[v],w[u][1]);
		else
			g[v]=max(g[v],w[u][0]);
		Dfs2(v);
	}
}

剩下的输出点的话就去找端点就$ok$啦，详细见代码

接下来是美滋滋的代码时间：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define N 500007
#define inf 0x3f3f3f3f 
using namespace std;
struct Edge
{
	int to,nxt; 
}edge[N<<1];
int n,cnt,ansmax,maxx,maxy,ansmin=inf,minx,miny;
int head[N],dep[N],f[N],d[N][3],w[N][2],lian[N],fa[N],g[N];
bool vis[N];
queue<int> q;
void Add(int u,int v)
{
	edge[++cnt]=(Edge){v,head[u]};
	head[u]=cnt;
}
void Dfs1(int u)
{
	for(int i=head[u];i;i=edge[i].nxt)
	{
		int v=edge[i].to;
		if(v==fa[u])//不是父亲 
			continue;
		dep[v]=dep[u]+1;//更新深度 
		fa[v]=u;//更新父亲节点 
		Dfs1(v);//递归 
		f[u]=max(f[u],f[v]);//更新以u根的子树最大直径，初始值为子树的最大直径 
		int tmp=d[v][0]+1;
		if(tmp>d[u][0])//更新d数组 
		{
			d[u][2]=d[u][1];
			d[u][1]=d[u][0];
			d[u][0]=tmp;
		}
		else
			if(tmp>d[u][1])
			{
				d[u][2]=d[u][1];
				d[u][1]=tmp;
			}
			else
				if(tmp>d[u][2])
					d[u][2]=tmp;
		tmp=f[v];
		if(tmp>w[u][0])//更新w数组 
		{
			w[u][1]=w[u][0];
			w[u][0]=tmp;
		}
		else
			if(tmp>w[u][1])
				w[u][1]=tmp;
	}
	f[u]=max(f[u],d[u][0]+d[u][1]);//更新直径 
}
void Dfs2(int u)
{
	if(u!=1)
	{
		if(ansmax<g[u]+f[u]+1)
		{
			ansmax=g[u]+f[u]+1;
			maxx=fa[u],maxy=u;
		}
		int tmp=max(max(f[u],g[u]),(f[u]+1)/2+(g[u]+1)/2+1);
		if(ansmin>tmp)
		{
			ansmin=tmp;
			minx=fa[u],miny=u;
		}
	}
	for(int i=head[u];i;i=edge[i].nxt)
	{
		int v=edge[i].to;
		if(v==fa[u])
			continue;
		lian[v]=max(lian[v],lian[u]+1);
		g[v]=max(g[v],g[u]);
		int tmp=d[v][0]+1;
		if(tmp==d[u][0])
		{
			g[v]=max(max(g[v],d[u][1]+d[u][2]),lian[u]+d[u][1]);
			lian[v]=max(lian[v],d[u][1]+1);
		}
		else
			if(tmp==d[u][1])
			{
				g[v]=max(max(g[v],d[u][0]+d[u][2]),lian[u]+d[u][0]);
				lian[v]=max(lian[v],d[u][0]+1);
			}
			else
			{
				g[v]=max(max(g[v],d[u][0]+d[u][1]),lian[u]+d[u][0]);
				lian[v]=max(lian[v],d[u][0]+1);
			}
		tmp=f[v];
		if(tmp==w[u][0])
			g[v]=max(g[v],w[u][1]);
		else
			g[v]=max(g[v],w[u][0]);
		Dfs2(v);
	}
}
int Bfs(int x)
{
	memset(vis,false,sizeof(vis));
	vis[x]=true;
	q.push(x);
	int ret;
	while(!q.empty())
	{
		int u=q.front();
		ret=u;
		q.pop();
		for(int i=head[u];i;i=edge[i].nxt)
		{
			int v=edge[i].to;
			if((u==minx&&v==miny)||(u==miny&&v==minx)||vis[v])
				continue;
			q.push(v);
			vis[v]=true;
		}	
	}
	return ret;
}
int Get(int x,int y,int len)
{
	int now=len;
	if(dep[x]<dep[y])
		swap(x,y);
	while(now!=(len+1)/2)
		x=fa[x],--now;
	return x;
}
void Outputmax()
{
	printf("%d %d %d ",ansmax,maxx,maxy);
	memset(vis,false,sizeof(vis));
	vis[maxx]=true;
	q.push(maxx);
	while(!q.empty())
	{
		int u=q.front();
		maxx=u;
		q.pop();
		for(int i=head[u];i;i=edge[i].nxt)
		{
			int v=edge[i].to;
			if((v==maxx||v==maxy)||vis[v])
				continue;
			q.push(v);
			vis[v]=true;
		}	
	}
	vis[maxy]=true;
	q.push(maxy);
	while(!q.empty())
	{
		int u=q.front();
		maxy=u;
		q.pop();
		for(int i=head[u];i;i=edge[i].nxt)
		{
			int v=edge[i].to;
			if(vis[v])
				continue;
			q.push(v);
			vis[v]=true;
		}	
	}
	printf("%d %d\n",maxx,maxy);
}
int main()
{
	freopen("2.in","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<n;++i)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		Add(u,v);
		Add(v,u);
	}
	Dfs1(1); Dfs2(1);
	printf("%d %d %d ",ansmin,minx,miny);
	int dianx1=Bfs(minx),diany1=Bfs(dianx1);
	int dianx2=Bfs(miny),diany2=Bfs(dianx2);
	printf("%d %d\n",Get(dianx1,diany1,g[miny]),Get(dianx2,diany2,f[miny]));
	Outputmax();
	return 0;
}