树的直径性质
摘自oi-wiki。
定理：在一棵树上，从任意节点 \(y\) 开始进行一次 DFS，到达的距离其最远的节点 \(z\) 必为直径的一端。
（证明通过反证法即可）（注意此定理建立在边权为正的基础上）
树的直径求法
由上面的定理诞生了一种求法：通过两次 \(dfs\) 找最远点即可。
另一种则是树形 \(dp\)（对链分类讨论即可）。
树形 \(dp\) 实现：
vector
int dp[2005],ans;
void dfs(int x,int fa){
dp[x]=0; int max1=0,max2=0;
for(int i:v[x])
if(i!=fa){
dfs(i,x); int mm=dp[i]+1;
if(mm>=max1)max2=max1,max1=mm;
else if(mm>=max2)max2=mm;
}
dp[x]=max1,ans=max(ans,max1+max2);
}
一般来说，树形 \(dp\) 码量（其实都很少）和适用范围都较两次 \(dfs\) 更优。
难道上面的定理纯废物吗？非也。
例题
城镇
L国一共有N座城镇，开始时它们两两不连通。L国计划依次建造N-1条道路，把所有城镇连通起来。
每建完一条道路，你需要回答这条道路所在连通块内距离最远的两座城镇之间的距离。
N≤300000
不难想到分类讨论：
合并两个联通块时，
直径要么在原子树中，要么经过新建的边（废话）。
第一种情况可以将信息存在并查集根节点上，
第二种情况可以考虑维护原子树的最长根链，将其合并即可。
你想到了什么？对，就是上面的定理！直径的端点之一就是最长根链的另一端。
这个也可以用并查集根节点存储（万能的根节点，联通块信息都可以存）。
代码实现：
#include
#include
#include
using namespace std;
constexpr int N=3e5+5;
int n,a1[N],a2[N];
vector
int fa[N],son[N],siz[N],dep[N],top[N];
int e1[N],e2[N];
struct DisJoint_Set{
int f[N];
void clear(){ for(int i=1;i<=n;i++)f[i]=i; }
int find(int x){ return (x==f[x])?x:f[x]=find(f[x]); }
void merge(int x,int y){
if(dep[find(x)]>dep[find(y)])f[find(x)]=find(y);
else f[find(y)]=find(x);
}
}s;
void dfs1(int x,int ffa){
fa[x]=ffa,dep[x]=dep[ffa]+1,siz[x]=1;
for(int i:v[x])if(i!=ffa){
dfs1(i,x),siz[x]+=siz[i];
if(siz[son[x]] } }void dfs2(int x,int t){ top[x]=t; if(son[x])dfs2(son[x],t); for(int i:v[x])if(i!=fa[x]&&i!=son[x])dfs2(i,i); }int LCA(int x,int y){ while(top[x]!=top[y]){ if(dep[top[x]] x=fa[top[x]]; }return (dep[x] }struct Cho{ int e1,e2,len; void get_len(){ int lca=LCA(e1,e2); len=dep[e1]+dep[e2]-2*dep[lca]; }void insert(int x,int y){ e1=x,e2=y,get_len(); }bool operator <(const Cho &x)const{ return len>x.len; } }a[10]; signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n; s.clear(); for(int i=1;i cin>>a1[i]>>a2[i], v[a1[i]].push_back(a2[i]), v[a2[i]].push_back(a1[i]); dfs1(1,0),dfs2(1,1); for(int i=1;i<=n;i++)e1[i]=e2[i]=i; for(int i=1;i int x=a1[i],y=a2[i]; x=s.find(x),y=s.find(y); a[1].insert(e1[x],e2[x]); a[2].insert(e1[y],e2[y]); a[3].insert(e1[x],e2[y]); a[4].insert(e1[y],e2[x]); a[5].insert(e1[x],e1[y]); a[6].insert(e2[x],e2[y]); sort(a+1,a+7); s.merge(x,y); x=s.find(x); e1[x]=a[1].e1,e2[x]=a[1].e2; cout< }return 0; }