》》》算法竞赛
/**
* @file
* @author jUicE_g2R(qq:3406291309)————彬(bin-必应)
* 一个某双流一大学通信与信息专业大二在读
*
* @brief 一直在竞赛算法学习的路上
*
* @copyright 2023.9
* @COPYRIGHT 原创技术笔记：转载需获得博主本人同意，且需标明转载源
* @language C++
* @Version 1.0还在学习中
*/
- UpData Log👆 2023.9.27 更新进行中
- Statement0🥇 一起进步
- Statement1💯 有些描述是个人理解，可能不够标准，但能达其意
技术提升站点
21-1 树的直径
21-1-1 定义
树上 最远的两个节点之间 的距离被称为 树的直径，连接这两个点的路径 被称为 树的最长链。
21-1-2 性质
- 1 、这两个最远点一定是叶子节点 1、这 两个最远点 一定是 叶子节点 1、这两个最远点一定是叶子节点
- 2 、距任意结点最远的点一定是直径的端点 2、距 任意结点最远的点 一定是 直径的端点 2、距任意结点最远的点一定是直径的端点
- 3 、两棵树相连，新树的直径的两端点一定是原四个端点中的两个 3、两棵树相连，新树的直径的两端点一定是原四个端点中的两个 3、两棵树相连，新树的直径的两端点一定是原四个端点中的两个
- 4 、若一棵树存在多条直径，多条直径交于一点，且交点是直径的严格中点（中点可能在某条边内） 4、若一棵树存在多条直径，多条直径交于一点，且交点是直径的严格中点（中点可能在某条边内） 4、若一棵树存在多条直径，多条直径交于一点，且交点是直径的严格中点（中点可能在某条边内）
21-1-3 实现的方法 及 选择
1）做两次DFS（或BFS）
2）树形DP
| 操作方法 | 优点 | 缺点 |
|---|---|---|
| 做两次DFS（或BFS） | 可以得到完整的路径，从而得到点与点之间的距离 | 不能用于有 负权值 的树 |
| 树形DP | 能用于有 负权值 的树 | 不可以得到完整的路径 |
树的直径
Input
就测试一个边上权值都为1的满二叉树
7 1 2 1 1 3 1 2 4 1 2 5 1 3 6 1 3 7 1Output
4
直通车——>树的存储方法：链式前向星
21-1-4 法一：做两次DFS（或BFS）
- 从任意 u 结点 u结点 u结点 出发，离 u 结点 u结点 u结点 最远的 e 结点 e结点 e结点，一定是该树直径的其中一个端点（性质2）
- 从得到的这个 e 结点 e结点 e结点 出发，离 u 结点 u结点 u结点 最远的 s 结点 s结点 s结点，一定是该树直径的其中另一个端点（性质2，定义）
- s 结点 s结点 s结点 与 e 结点 e结点 e结点 就是这棵树直径的端点
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int> head(N,-1);
struct Edge{ //链式前向星
int to,next;
int weight;
Edge():to(-1), next(-1){} //初始化为无邻居节点
} edge[N<<1];
int n; //人有n个，关系有n-1条
int cot=0;
vector<int> dis(N,0); //记录距离
void Add_Edge(int u, int v,int w){
edge[cot].to=v;
edge[cot].weight=w;
edge[cot].next=head[u]; //记录 上一个邻居节点 的 存储编号
head[u]=cot++; //当前 邻居节点 的 存储编号，以便下一个邻居节点的访问
}
void DFS(int u, int father, int w){
dis[u]=dis[father]+w; //更新当前节点的距离
for(int i=head[u]; ~i; i=edge[i].next){ //遍历cur节点的邻居节点[~i相当于i=-1]
int v=edge[i].to; //v 是 u 的子节点
if(v==father) continue; //不遍历父节点
DFS(v, u, edge[i].weight);
}
}
int main(void){
int n; cin>>n;
for(int i=1; i<n; i++){
int u,v,w; cin>> u >> v >> w;
Add_Edge(u,v,w); Add_Edge(v,u,w); //无向 记录 双向有向
}
/*找到树直径的其中一个端点*/
DFS(1,0,0); //以 1号节点 为根节点遍历整个树，获得所有节点离节点1的距离
int n1_id=1; //初始化
for(int i=1; i<=n; i++) //遍历输入的n个结点
if(dis[i]>dis[n1_id]) //最终是为了找到到 结点1 距离最远的那个节点
n1_id=i;
/*找到树直径的另一端点*/
DFS(n1_id,0,0); //以 n1_id结点 为根节点开始遍历整棵树，最终最远的那个距离就是直径
int n2_id=1; //初始化
for(int i=1; i<=n; i++) //遍历输入的n个结点
if(dis[i]>dis[n2_id]) //最终是为了找到到 n1_id节点 距离最远的那个节点
n2_id=i;
cout<<dis[n2_id];
return 0;
}
//法一
void DFS(int u, int father, int w){
dis[u]=dis[father]+w; //更新当前节点的距离
for(int i=head[u]; ~i; i=edge[i].next){ //遍历cur节点的邻居节点[~i相当于i=-1]
int v=edge[i].to; //v 是 u 的子节点
if(v==father) continue; //不遍历父节点
DFS(v, u, edge[i].weight);
}
}
//法二
vector<bool> visit(N,false);
void DFS(int u, int father, int w){
dis[u]=dis[father]+w; //更新当前节点的距离
visit[u]=true; //标记为已访问，避免下次再访问
for(int i=head[u]; ~i; i=edge[i].next){
int v=edge[i].to; //v 是 u 的子节点
if(visit[v]) continue; //v已经算过了，避免重复遍历
DFS(v, u, edge[i].weight);
}
}
DFS(BFS)为何不能用在有 负权值 的树里呢？
很容易想到一个反例：离目标节点 的 倒数第二远的节点到最远的节点 这条边如果权值为负，会得出 dis[倒数第二远]>dis[最远的节点] 的错误结论。（是因为我们让权值和作为判断 是否远 的依据）
而我们比较depth，就可以解决这个问题。
21-1-5 法二：树形DP（动态规划）
直通车——>DP算法求最大子序和
为何 DP能解决 有 负权值 的树 的树直径问题？
-
以
贪心思想实现的DFS算法暴露的问题就是只满足 “局部最优，而不顾全局”，Dijkstra算法同理也不能使用在有 负权值 的树。 -
全局最优的
DP动态规划算法可以弥补这个短板，Floyd算法基于 DP 同理也能使用在有 负权值 的树。
如何实现 动态规划？
d
p
[
u
]
dp[u]
dp[u] 是 以 u结点 为根节点的子树上，从 u结点 出发能到达的最远路径的长度，这个路径的终点是 u结点子树 的叶子节点
- 状态转移方程
d p [ u ] = m a x ( d p [ v i ] + e d g e [ u , v i ] ) dp[u]=max(dp[v_i]+edge[u,v_i]) dp[u]=max(dp[vi]+edge[u,vi])【 v i v_i vi 是 u 结点 u结点 u结点 第 i 个邻居节点， e d g e [ u , v i ] edge[u,v_i] edge[u,vi] 是他们边上的权值】
- 每个结点的最长路径长度
将 u 节点 u节点 u节点 的每个结点的最长路径长度 记录在 a n s [ u ] ans[u] ans[u] 里
f [ u ] f[u] f[u] 状态转换方程： f [ u ] = m a x ( d p [ u ] + d p [ v i ] + e d g e [ u , v i ] ) f[u]=max(dp[u]+dp[v_i]+edge[u,v_i]) f[u]=max(dp[u]+dp[vi]+edge[u,vi])【此时的 d p [ u ] dp[u] dp[u] 是不包含 v i 子树 v_i子树 vi子树 的，即 d p [ u ] = m a x ( d p [ v i ] + e d g e [ u , v i ] ) dp[u]=max(dp[v_i]+edge[u,v_i]) dp[u]=max(dp[vi]+edge[u,vi]) 是在这个状态转化方程后执行的】文章来源：https://www.toymoban.com/news/detail-729963.html
maxlen=max(maxlen, dp[u]+dp[v]+edge[i].weight);
dp[u]=max(dp[u], dp[v]+edge[i].weight);
//注这里的 max函数 可以替换成 三目运算符 来实现
树的直径为 m a x l e n = m a x ( f [ u ] ) maxlen=max(f[u]) maxlen=max(f[u])，即 最大的 结点的最长路径长度（从定义出发考虑）文章来源地址https://www.toymoban.com/news/detail-729963.html
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int> head(N,-1);
struct Edge{ //链式前向星
int to,next;
int weight;
Edge():to(-1), next(-1){} //初始化为无邻居节点
} edge[N<<1];
int n; //人有n个，关系有n-1条
int maxlen=0; //树的直径
int cot=0;
vector<bool> visit(N,false);
vector<int> dp(N,0);
void Add_Edge(int u, int v,int w){
edge[cot].to=v;
edge[cot].weight=w;
edge[cot].next=head[u]; //记录 上一个邻居节点 的 存储编号
head[u]=cot++; //当前 邻居节点 的 存储编号，以便下一个邻居节点的访问
}
void DP(int u){
visit[u]=true; //标记为已访问，避免下次再访问
for(int i=head[u]; ~i; i=edge[i].next){ //遍历cur节点的邻居节点[~i相当于i=-1]
int v=edge[i].to; //v 是 u 的子节点
int u_v=edge[i].weight; //u 与 v 边上的权值
if(visit[v]) continue; //v已经算过了，避免重复遍历
DP(v);
maxlen=max(maxlen, dp[u]+dp[v]+u_v); //将当前值与历史最大比较
dp[u]=max(dp[u], dp[v]+u_v);
}
}
int main(void){
int n; cin>>n;
for(int i=1; i<n; i++){
int u,v,w; cin>> u >> v >> w;
Add_Edge(u,v,w); Add_Edge(v,u,w); //无向 记录 双向有向
}
DP(1);
cout<<maxlen;
return 0;
}
到了这里，关于【图论C++】树的直径（DFS 与 DP动态规划）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
