树的直径
定义 性质：
树的直径是树上最长的链，即树上任意两点间距离的最大值，可能有多条。
若树无边权，则所有直径的中点相同。
求法：
两次 \(DFS\)。
第一次，以任意节点为根，搜索到距离自己最远的点，这个点就是直径的一个端点。
第二次，以第一次求得的点为根，搜索到距离自己最远的点，这个点就是另一个端点。
长度和路径可以在 \(DFS\) 中求得。文章来源：https://www.toymoban.com/news/detail-843841.html
时间复杂度：\(\Theta(N)\)文章来源地址https://www.toymoban.com/news/detail-843841.html
代码：
#include<iostream>
#include<vector>
#include<cstring>
#define int long long
using namespace std;
const int N = 100010;
int n;
vector<int> G[N];
int le, n1, n2, dia[N]; // 直径长度，一个端点，dfs次数，节点
int de[N];
void predfs(int u, int fa)
{
if(de[u] > le)
{
le = de[u]; // 更新长度
n2 = u; // 更新端点
}
for(int i=0; i<G[u].size(); i++)
{
int v = G[u][i];
if(v == fa)
continue;
de[v] = de[u] + 1;
if(n1)
dia[v] = u; // 存储路径
predfs(v, u);
}
}
signed main()
{
cin >> n;
for(int i=1; i<n; i++)
{
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
predfs(1, 0);
memset(de, 0, sizeof(de));
le = 0, n1 = n2;
de[n2] = 1;
predfs(n2, 0);
cout << n1 << ' ' << n2 << ' ' << le << '\n';
// 端点和长度
int t = n2;
for(int i=1; i<=le; i++)
{
cout << t << ' ';
t = dia[t];
} // 路径
return 0;
}
到了这里，关于算法笔记 - 树的直径的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
