树上任意两节点之间最长的简单路径即为树的「直径」
如何求?
- $跑两遍DFS$
第一遍找到一条直径的端点
第二遍从端点出发跑到另一个端点 - $树形DP$
例题
直径
先跑两遍$DFS$找到一条直径,并记录上面的点
然后再对直径上的每一个点跑DFS(不能经过直径上的点)求出该点能到达的最远距离$exdis[]$
最后再找到从后往前第一个$i$使得$exdis[i] = dis[i]$那么说明从$i$点出发能到达另一个直径的端点
和从前往后第一个$j$使得$exdis[j] = dis[NODE] - dis[j]$那么说明从$j$点出发也能到达另一个直径的端点
那么夹在$i$和$j$之间的边就是公共边
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 200020;
int n, node, NODE;
LL dis[N], exdis[N], tmp;
int e[N << 1], ne[N << 1], w[N << 1], h[N], idx;
int head[N], last[N];
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u, int fa)
{
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i], v = w[i];
if (j == fa) continue;
dis[j] = dis[u] + v;
if (dis[j] > dis[node]) node = j;
dfs(j, u);
}
}
void DFS(int u, int fa)
{
head[u] = fa; // 记录一下这个点的上一个点是哪个点
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i], v = w[i];
if (j == fa) continue;
dis[j] = dis[u] + v;
if (dis[j] > dis[NODE]) NODE = j;
DFS(j, u);
}
}
void Dfs(int u, int fa, LL t)
{
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i], v = w[i];
if (st[j] || j == fa) continue;
tmp = max(tmp, t + v);
Dfs(j, u, t + v);
}
}
int main()
{
scanf ("%d", &n);
memset(h, -1, sizeof h);
for (int i = 1; i < n; i ++)
{
int a, b, c;
scanf ("%d %d %d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
dfs(1, 0); // 找出一条直径的端点
dis[node] = 0;
DFS(node, 0); // 找到另一个端点
printf ("%lld\n", dis[NODE]);
for (int i = NODE; i; i = head[i]) st[i] = true; // 标记一下这个直径上的所有点
// 求出直径上每一个点到非该直径上的点的最大距离
for (int i = NODE; i; i = head[i])
{
tmp = 0;
Dfs(i, 0, 0);
exdis[i] = tmp;
}
for (int i = head[NODE], j = NODE; i; i = head[i]) // 记录一下每一个点的下一个点是哪个点
{
last[i] = j;
j = i;
}
// 一定要是这个顺序,先从后往前找左端点,再从左端点往右找右端点
int now, res = 0;
for (now = head[NODE]; now; now = head[now])
if (dis[now] == exdis[now]) break;
for (; now; now = last[now])
if (dis[NODE] - dis[now] == exdis[now]) break;
else res ++;
printf ("%d", res);
return 0;
}