题解 P3596 【[POI2015]MOD】
3493441984zz
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$数组，详细过程在代码中注释了：
~~~cpp
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]$相加组成直径
代码：
~~~cpp
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]$相加组成直径
代码：
~~~cpp
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]$相加组成直径
代码：
~~~cpp
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$点，所以还要与它子节点为根的子树的直径取最大值
代码：
~~~cpp
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$之间的边后，把两端相连就是最长直径，也就是
~~~cpp
if(ansmax<g[u]+f[u]+1)
{
ansmax=g[u]+f[u]+1;
maxx=fa[u],maxy=u;
}
~~~
而最小值就是两个直径中点相连，也就是
~~~cpp
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$可以直接搞出来
代码：
~~~cpp
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$啦，详细见代码
接下来是美滋滋的代码时间：
~~~cpp
#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;
}
~~~