CX.[POI2015]MOD
比较恶心的题目。
首先，有一个结论，即如果把两棵树通过某种方式连接起来，新树的直径的端点一定来自于原本两棵树的直径端点集合。
则考虑新树的最大直径，明显就是把两棵树的直径直接连一块，就是两棵树的直径之和再加一。
考虑新树的最小直径，则应该选择两树直径的中点（如果直径长度为奇数则随便选一个）连一块，这样新树的直径就是 \(\left\lceil\dfrac{\text{直径一}}{2}\right\rceil+\left\lceil\dfrac{\text{直径二}}{2}\right\rceil+1\)。当然，还得与两条直径本身取一个\(\max\)。
于是我们就用换根DP求出\(g_x\)表示\(x\)子树内的直径，\(h_x\)求出其子树外的直径（这里换根DP我一开始用的是multiset维护，但是会莫名其妙MLE。故最后不得不全面换成vector才不出问题）。然后两个拼一块就能找出所有新树的直径的最大值/最小值。
代码（非常丑陋）：
#include<bits/stdc++.h>
using namespace std;
int n,f[500100],g[500100],h[500100],FA[500100],mx,mn=0x3f3f3f3f;
//f[i]:the maximal length starting from i; g[i]: the maximal length in i's subtree; h[i]:the maximal length outside that.
vector<int>v[500100],s[500100],t[500100];
void dfs1(int x,int fa){
for(auto y:v[x]){
if(y==fa)continue;
FA[y]=x;
dfs1(y,x);
f[x]=max(f[x],f[y]+1);
s[x].push_back(f[y]+1);
t[x].push_back(g[y]);
g[x]=max(g[x],g[y]);
}
sort(s[x].rbegin(),s[x].rend());while(s[x].size()>3)s[x].pop_back();
sort(t[x].rbegin(),t[x].rend());while(t[x].size()>2)t[x].pop_back();
if(s[x].size()>=2)g[x]=max(g[x],s[x][0]+s[x][1]);
else if(s[x].size()>=1)g[x]=max(g[x],s[x][0]);
}
void dfs2(int x,int fa){
int alls=0;
for(auto i:s[x])alls+=i;
// printf("%dS",x);for(auto i:s[x])printf("%d ",i);puts("");
// printf("%dT",x);for(auto i:t[x])printf("%d ",i);puts("");
for(auto y:v[x]){
if(y==fa)continue;
if(f[y]+1>=s[x].back())h[y]=alls-(f[y]+1);
else if(s[x].size()<=2)h[y]=alls;
else h[y]=s[x][0]+s[x][1];
if(t[x][0]!=g[y])h[y]=max(h[y],t[x][0]);
else if(t[x].size()>=2)h[y]=max(h[y],t[x][1]);
t[y].push_back(h[y]);
sort(t[y].rbegin(),t[y].rend());while(t[y].size()>2)t[y].pop_back();
if(s[x][0]!=f[y]+1)s[y].push_back(s[x][0]+1);
else if(s[x].size()>=2)s[y].push_back(s[x][1]+1);
else s[y].push_back(1);
sort(s[y].rbegin(),s[y].rend());while(s[y].size()>3)s[y].pop_back();
dfs2(y,x);
}
}
int S,dp,inva,nd,rt;
void dfs3(int x,int fa,int dep){
if(dep>dp)S=x,dp=dep;
for(auto y:v[x])if(y!=fa&&y!=inva)dfs3(y,x,dep+1);
}
bool dfs4(int x,int fa){
if(x==S){
nd--;
if(nd==0)rt=x;
return true;
}
for(auto y:v[x]){
if(y==fa)continue;
if(!dfs4(y,x))continue;
nd--;
if(nd==0)rt=x;
return true;
}
return false;
}
int main(){
scanf("%d",&n);
for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
dfs1(1,0),dfs2(1,0);
// for(int i=1;i<=n;i++)printf("%d:%d %d %d\n",i,f[i],g[i],h[i]);
for(int i=2;i<=n;i++)mx=max(mx,g[i]+h[i]+1),mn=min(mn,max({(g[i]+1)/2+(h[i]+1)/2+1,g[i],h[i]}));
for(int i=2;i<=n;i++){
if(mn!=max({(g[i]+1)/2+(h[i]+1)/2+1,g[i],h[i]}))continue;
printf("%d %d %d ",mn,i,FA[i]);
inva=FA[i];
S=0,dp=-1;
dfs3(i,FA[i],0);
int T=S;
S=0,dp=-1;
dfs3(T,0,0);
nd=(g[i]+2)/2;
dfs4(T,0);
printf("%d ",rt);
inva=i;
S=0,dp=-1;
dfs3(FA[i],i,0);
T=S;
S=0,dp=-1;
dfs3(T,0,0);
nd=(h[i]+2)/2,dfs4(T,0);
printf("%d\n",rt);
break;
}
for(int i=2;i<=n;i++){
if(mx!=g[i]+h[i]+1)continue;
inva=0;
printf("%d %d %d ",mx,i,FA[i]);
S=0,dp=-1;
dfs3(i,FA[i],0);
printf("%d ",S);
S=0,dp=-1;
dfs3(FA[i],i,0);
printf("%d\n",S);
break;
}
return 0;
}