树的直径：
-
定义：树上两个距离最远的点形成的简单路径（不重复走一条边 / 点）
-
性质：
-
不唯一。
-
树的直径的端点一定是度数为 \(1\) 的点。
证明：显然。
-
树的直径若有多条，则必交汇于一点，即中心。
证明：首先每条直径只能交于端点（因为是一棵树，一个节点不能有两个父节点），然后此交点必定为最长链最短的节点即中心（因为它度数为 \(1\)，没有父节点，并且它的子节点的最长链是子节点到它的距离加上直径，一定不比直径小）。
-
树上任意点 \(u\) 距离其最远的点一定为树的直径的端点。
证明：根据直径最长的定义易证。
-
-
求法：
-
2 遍 dfs
-
原理：性质三。
-
从任意点 \(u\) 出发 dfs 找到距 \(u\) 最远的点 \(x\)，\(x\) 为端点；
-
从 \(x\) 出发找到距 \(x\) 最远的点 \(y\)，\(y\) 为端点；
-
\(x \to y\) 的简单路径即为树的一条直径。
\(O(n)\)，仅用于边权非负的树。
-
-
-
树形 dp
-
原理：性质二，枚举中心，将最长链与次长链拼接。
-
定义
dis1[i]表示以点i为根的最长链，dis2[i]为次长链； -
转移：
dfs(nxt,cur); //先递归再转移 if(dis1[nxt]+w>dis1[cur]) dis2[cur]=dis1[cur], dis1[cur]=dis1[nxt]+w; else if(dis1[nxt]+w>dis2[cur]) dis2[cur]=dis1[nxt]+w;- 枚举点
i，取max(dis1[i]+dis2[i])即为直径长度。
\(O(n)\)，可以有负边权。
-
-
-
https://www.luogu.com.cn/problem/SP1437
板子。
法一
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,x,dis;
struct edge{ int v,w; };
vector<edge> G[N];
bool vis[N];
void dfs(int cur,int sum){
vis[cur]=1;
if(sum>=dis)
dis=sum,x=cur;
for(auto i:G[cur])
if(!vis[i.v])
dfs(i.v,sum+i.w);
}
int main(){
cin>>n;
for(int i=1;i<n;i++){
int u,v,w; cin>>u>>v>>w;
G[u].push_back({v,w}),
G[v].push_back({u,w});
}
dfs(1,0);
memset(vis,0,sizeof vis);
dfs(x,0);
cout<<dis;
return 0;
}
法二
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,x,ans;
struct edge{
int v,w;
};
vector<edge> G[N];
int dis1[N],dis2[N];
void dfs(int cur,int fa){
for(auto i:G[cur]){
if(i.v==fa) continue;
dfs(i.v,cur);
if(dis1[i.v]+i.w>dis1[cur])
dis2[cur]=dis1[cur],
dis1[cur]=dis1[i.v]+i.w;
else if(dis1[i.v]+i.w>dis2[cur])
dis2[cur]=dis1[i.v]+i.w;
}
ans=max(ans,dis1[cur]+dis2[cur]);
}
int main(){
cin>>n;
for(int i=1;i<n;i++){
int u,v,w; cin>>u>>v>>w;
G[u].push_back({v,w}),
G[v].push_back({u,w});
}
dfs(1,-1);
cout<<ans;
return 0;
}
https://www.luogu.com.cn/problem/CF455C & https://www.luogu.com.cn/problem/P2195
我们发现两个树连边连中心得到的新树直径最短（由中心的定义易证）。
然后我们发现中心的一个性质：当中心为根时，其到直径两端点的距离分别为最长和非严格次长链（由直径的定义易证），又因为中心的最长链最短，于是这相当于中心将直径劈成了两半，每一半都是 \(\lceil \frac{直径长度}{2} \rceil\)。
因此我们用并查集虚拟连边维护联通性（假定以中心为根），并维护每个节点所在树的直径这一信息，每次连边的新直径即为 \(\max(z_x,z_y,\lceil \frac{z_x}{2} \rceil + \lceil \frac{z_y}{2} \rceil + 1)\)（\(z_x,z_y\) 表示要连边的两点 \(x,y\) 所在树的直径）。
code
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,m,q;
vector<int> G[N];
int x,dis;
int fa[N],z[N];
void dfs(int cur,int fa,int sum){
if(sum>=dis)
dis=sum,x=cur;
for(int i:G[cur])
if(i!=fa)
dfs(i,cur,sum+1);
}
int fnd(int x){
return (x==fa[x]?x:fa[x]=fnd(fa[x]));
}
void uni(int x,int y){
x=fnd(x),y=fnd(y);
if(x!=y)
z[y]=max((z[x]+1)/2+(z[y]+1)/2+1,max(z[x],z[y])),
fa[x]=y;
}
int main(){
ios::sync_with_stdio(0);
cin>>n>>m>>q;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1,u,v;i<=m;i++)
cin>>u>>v,
G[u].push_back(v),
G[v].push_back(u),
uni(u,v);
for(int i=1;i<=n;i++){
if(fa[i]==i){
x=dis=0;
dfs(i,0,0),dfs(x,0,0);
z[i]=dis;
}
}
while(q--){
int op,x,y; cin>>op>>x;
if(op==1) cout<<z[fnd(x)]<<'\n';
else cin>>y,uni(x,y);
}
return 0;
}
https://www.luogu.com.cn/problem/CF1404B
Case 1：一步到位。\(dis_{a,b} \le da\)。
Case 2：Alice 必然会将 Bob 赶进某棵子树，则 Bob 就会在某一时刻折返，此时 Alice 仅需走 Bob 一半及以上距离即可。\(2da \ge db\)。
Case 3：Alice 在中心时，仅需覆盖最长链即可覆盖整棵树。\(\lceil \frac{树的直径}{2} \rceil \le da\)。
code
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int t,n,a,b,da,db;
int x,dis,disab;
vector<int> G[N];
void dfs(int cur,int fa,int sum){
if(sum>=dis)
dis=sum,x=cur;
for(int i:G[cur])
if(i!=fa)
dfs(i,cur,sum+1);
}
void dfsab(int cur,int fa,int sum){
if(cur==b){
disab=sum; return;
}
for(int i:G[cur])
if(i!=fa)
dfsab(i,cur,sum+1);
}
void init(){
x=dis=disab=0;
for(int i=1;i<=n;i++) G[i].clear();
}
void sol(){
init();
cin>>n>>a>>b>>da>>db;
for(int i=1,u,v;i<n;i++)
cin>>u>>v,
G[u].push_back(v),
G[v].push_back(u);
dfs(1,0,0),dfs(x,0,0),dfsab(a,0,0);
//cout<<dis<<' '<<disab<<'\n';
if(da>=disab) cout<<"Alice\n";
else if(da>=(dis+1)/2) cout<<"Alice\n";
else if(2*da>=db) cout<<"Alice\n";
else cout<<"Bob\n";
}
int main(){
cin>>t;
while(t--) sol();
return 0;
}