CF 1092E Minimal Diameter Forest 题解

Solution 1

首先，如果我们已经把这棵可爱的森林连成了一棵更加可爱的树，那么新树的直径是多少呢？

类比CF804D（有我题解），可以得到直径来自下面两种情况之一：

①老树中的直径(即在初始的森林形态时的每棵树)；

②对于两个来自不同老树的节点$u,v$后，它们之间的长度为:

$u$所在的老树中，以$u$为一端的路径的最长链+

在新树中，$u$所在的树与$v$所在的树的距离+

$v$所在的老树中，以$v$为一端的路径的最长链。

首先，我们考虑该如何连接节点，不考虑在哪些老树之间连边。显然，假设我们连接了节点$u,v$，那么$u,v$一定是所在老树中直径(最长链)的中点。

此定理很显然，读者自证不难

在初始的森林形态中，定义有$k$棵树，$d_i$表示在第$i$棵树中以直径的中点为一端的路径的最长距离，$dis(i,j)$表示第$i$棵树到第$j$棵树的距离，$di{a}_i$表示第$i$棵树的直径。我们需要用一种方式来连接这些树，使得

$f=ma{x}_{1\le i\le k,1\le j\le k,i?=j}(max(d_i+d_j+dis(i,j),di{a}_i,di{a}_j))$

的值最小。

现在，相当于，我们把原来的树套树缩成了一棵普通的树，每个节点都有一个点权$d$；现在要把这些节点连成一棵树，使得$f$值最小。

这时，我们需要的就是构造的能力。接着可以发现，我们构造出来的树必须是一个菊花图。

为什么呢？这里帮助各位巨佬感性理解一下：菊花图有一个重要的性质，其直径为$2$。所以，$dis(i,j)$的最大值也只有$2$。

详细证明咕咕咕

于是，我们枚举菊花图的那个入度为$k?1$的节点，假设$t$是目前枚举到的这个节点的编号。每次求出$f$的值。而$f$的值似乎只能在$O(k^2)$的复杂度内求出……

考虑优化一下求$f$值的方法。根据$max$函数的结合律，我们可以得到：

$f=ma{x}_{1\le i\le k,1\le j\le k,i?=j}(max(d_i+d_j+dis(i,j),di{a}_i,di{a}_j))$

$f=max(ma{x}_{1\le i\le k,1\le j\le k,i?=j}(d_i+d_j+dis(i,j)),ma{x}_{1\le i\le k}(di{a}_i))$

①当$dis(i,j)=1$时，显然$i=t$或$j=t$。直接枚举找最大值即可，时间复杂度为$O(k)$。

②当$dis(i,j)=2$时，显然$i?=t$切$j?=t$。此时的最大值为$d$数组中除去编号为$t$的节点后，剩下的最大值与次大值之和加$2$。于是，我们每次只需要找最大值与次大值即可，时间复杂度为$O(k)$。

在最坏情况下，$k=n$，此时时间复杂度为$O(n^2)$。

Solution 2

本文章开头说过，本题存在$O(nlogn)$或$O(n)$的解法。

现在，我们回过头来看，Soluion 1中有什么可以优化的呢？

①当$dis(i,j)=1$时，我们不需要枚举最大值。最大值即为$t$号节点的$d$值，与剩下节点$d$值的最大值之和加$1$。

②只需要每次$O(1)$找到除去$t$节点的最大值与次大值即可优化。

于是，现在我们需要攻克的最后一个关卡就是一个Answer Queries的问题: 每次查询去掉一个节点后，剩下节点的最大值与次大值；每次询问独立。

这个问题有两种做法：

①求出$d$数组后立即$O(klogk)$地排序；

②求出$d$数组后，在$O(k)$的复杂度内求出其最大值，次大值与次次大值(即第$3$大的值)，每次就可以$O(1)$查询。

最后，我们得到了本题的正解，而它是$O(n)$的。

但是由于本蒟蒻过于懒惰，采用了$O(nlogn)$的做法QAQ

Summary

步骤:

①通过并查集找到森林中的每棵树；

②求出每棵树的直径，与$d$值(直径可以通过两次$dfs$求出)；

③枚举菊花图的度数为$k?1$的节点，并求出$f$来更新答案。

本题思维含量较高，是$Div.3$的$E$中偏难的好题，但并不难得到正解。套路性强，码量较大，数据太水。

Code

//O(nlogn)解法
#include <bits/stdc++.h>
#define int long long
#define inf 200000000000007
using namespace std;int n,m,u,v,cnt=0,len=0,maxv=0,ans=inf,poss;
int head[100005],size[100005],depth[100005],father[100005];
int pos[100005],up[100005],bestson[100005],top[100005];struct FFT
{int rt,dia,d,minrt;	
}ducati[200005];struct edge
{int next;int to;
}e[200005];struct node
{int u,v;
}a[100005];inline void add_edge(int u,int v)
{cnt++;e[cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
}inline int find(int x)
{if (x!=father[x])  father[x]=find(father[x]);return father[x];
}inline void dfs(int now,int fath,int nowdis)
{up[now]=fath;size[now]=1;depth[now]=depth[fath]+1;int Maxv=0;if (nowdis>=maxv)  maxv=nowdis,u=now;for (int i=head[now];i;i=e[i].next){if (e[i].to!=fath){dfs(e[i].to,now,nowdis+1);size[now]+=size[e[i].to];if (size[e[i].to]>Maxv)  Maxv=size[e[i].to],bestson[now]=e[i].to;}}
}inline void dfs1(int now,int fath,int nowtop)
{top[now]=nowtop;if (bestson[now])  dfs1(bestson[now],now,nowtop);for (int i=head[now];i;i=e[i].next){if (e[i].to!=fath&&e[i].to!=bestson[now])  dfs1(e[i].to,now,e[i].to);}
}inline void dfs2(int now,int fath,int nowdis)
{if (now==1)  return;if (nowdis>=maxv)  maxv=nowdis,v=now;for (int i=head[now];i;i=e[i].next){if (e[i].to!=fath)  dfs2(e[i].to,now,nowdis+1);}
}inline int LCA(int x,int y)
{while (top[x]!=top[y]){if (depth[top[x]]<depth[top[y]])  swap(x,y);x=up[top[x]];}if (depth[x]<depth[y])  return x;else return y;
}inline int dis(int x,int y)
{int tmp=LCA(x,y);return depth[x]-depth[tmp]+depth[y]-depth[tmp];
}inline void dfs3(int now,int fath)
{int res=max(dis(now,u),dis(now,v));if (ducati[len].d>=res){ducati[len].d=res;ducati[len].minrt=now-1;}for (int i=head[now];i;i=e[i].next){if (e[i].to!=fath)  dfs3(e[i].to,now);}
}bool cmp(FFT x,FFT y)
{return x.d>y.d;
}signed main()
{cin>>n>>m;for (int i=1;i<=n+1;i++)  father[i]=i;for (int i=1;i<=m;i++){cin>>u>>v;u++,v++;if (u>v)  swap(u,v);father[find(u)]=find(v);a[i].u=u,a[i].v=v;add_edge(u,v);add_edge(v,u);}for (int i=1;i<=n+1;i++)  father[i]=find(father[i]);for (int i=2;i<=n+1;i++){if (i==father[i])  add_edge(1,i),add_edge(i,1);}for (int i=head[1];i;i=e[i].next){len++;ducati[len].d=inf;pos[e[i].to]=len;maxv=0;dfs(e[i].to,1,0);dfs1(e[i].to,1,e[i].to);maxv=0;dfs2(u,1,0);dfs3(e[i].to,1);ducati[len].dia=dis(u,v);ducati[len].rt=e[i].to;}if (len==1)  return cout<<ducati[len].dia<<endl,0;else if (len==2){int ans=max(ducati[1].d+ducati[2].d+1,max(ducati[1].dia,ducati[2].dia));cout<<ans<<endl;cout<<ducati[1].minrt<<' '<<ducati[2].minrt<<endl;return 0;}sort(ducati+1,ducati+len+1,cmp);maxv=0;for (int root=1;root<=len;root++)  maxv=max(maxv,ducati[root].dia);for (int root=1;root<=len;root++){int point=1,point2=2,now=0;if (root==1)  point=2;now=max(now,ducati[root].d+ducati[point].d+1);if (root==1)  point=2,point2=3;else if (root==2)  point=1,point2=3;now=max(now,ducati[point].d+ducati[point2].d+2);now=max(now,maxv);if (now<ans){ans=now;poss=root;}}cout<<ans<<endl;for (int i=1;i<=len;i++){if (i==poss)  continue;cout<<ducati[poss].minrt<<' '<<ducati[i].minrt<<endl;}return 0;
}