2/3树的直径等内容 学习总结

树的直径值树中最长的简单路径，一般用两次dfs和树形dp求，是数据结构中常见常考的重点之一。

两次dfs求树的直径

求法

从任意点dfs一次，找到距离该点最远的点，记为点 \(s\)。

从 \(s\) 出发再dfs一次，找到距离最远的点，记为点 \(t\)。

\(s\) 到 \(t\) 的简单路径一定是树的直径之一。

证明

如上图

根据定义，不存在 \(u\) 使得 \(|u\rightarrow s|>|t\rightarrow s|\)

如果存在节点 \(u\)，使得 \(|u\rightarrow t|>|s\rightarrow t|\)

那么 \(|n\rightarrow u|>|n\rightarrow s|\)，故 \(|1\rightarrow u|>|1\rightarrow s|\)

第一次搜索就会搜到 \(u\) 而不是 \(s\)。

故假设矛盾，所以不存在任何一点，到 \(s\) 或者 到 \(t\) 的距离，比 \(|s\rightarrow t|\) 更远 。

证毕

注意事项

1.必须全是非负权边

\(\mathscr{A\rightarrow^{10}B\rightarrow^{-1000}C\rightarrow^{1000}D}\)

如果搜索的起点选择了 \(\mathscr{D}\)，可以求出直径。但是如果选择了 \(\mathscr{B}\)，则求不出直径。

代码

1.有多个dfs/bfs时，函数名不能是其他函数名的前缀，变量名同理。

$\surd$

void dfs1(...)

void dfs2(...)

$\times$(打错了就很难调）

void dfs(...)

void dfs2(...)

AC code

#include<bits/stdc++.h>
using namespace std;
int d1[100005],d2[100005];
vector<int> g[100005];
void dfs1(int x,int fa){for(auto y:g[x]){if(y==fa) continue;d1[y]=d1[x]+1;dfs1(y,x);}
}
void dfs2(int x,int fa){for(auto y:g[x]){if(y==fa) continue;d2[y]=d2[x]+1;dfs2(y,x);}
}
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);int n;cin>>n;for(int i=1;i<n;i++){int x,y;cin>>x>>y;g[x].push_back(y);g[y].push_back(x);}dfs1(1,0);int maxn=0,s=0;for(int i=1;i<=n;i++){if(d1[i]>=maxn){s=i;maxn=d1[i];}}dfs2(s,0);int maxm=0,t=0;for(int i=1;i<=n;i++){if(d2[i]>=maxm){t=i;maxm=d2[i];}}cout<<d2[t];return 0;
}

树形dp求树的直径

求法

记录 \(d1[u]\) 为以 \(u\) 为根的子树中，从 \(u\) 出发向下的最长路径。

\(d2[u]\) 为以 \(u\) 为根的子树中，从 \(u\) 出发向下的次长路径。(\(\Large{不与最长路径重合！}\))

遍历时 \(u\) 的儿子 \(v\) 会贡献长度 \(len=d1[v]+w(u,v)\) 的路径，此时：

如果 \(len>d1[u]\)，说明找到了更长的路径，\(d2[u]=d1[u]\)，\(d1[u]=len\)。

否则如果 \(len>d2[u]\)，说明比次长的长，比最长的短，只需更新次长的。\(d2[u]=len\)。