ToB企服应用市场:ToB评测及商务社交产业平台

标题: 树的直径 [打印本页]

---

作者: 麻花痒    时间: 2022-8-10 10:02
标题: 树的直径
一、树的直径的定义：最长的一条链。
二、求法
1．两次bfs（或者dfs）求树的直径
优点：可以求出路径。
缺点：时间复杂度O(2*N)， 在负权边中无法使用。
方法：先从任意一点出发，找离它最远的点P，再从点P出发，找离它最远的点Q，P到Q的距离就是树的直径。
代码：

1. inline void dfs(int u, int f, int & tar)
2. {
3.         int v;
4.         for(int e = hd[u]; e; e = nt[e])
5.             if((v = to[e]) ^ f)
6.             {
7.                     dis[v] = dis[u] + w[e];
8.                     if(dis[v] > dis[tar]) tar = v;
9.                     dfs(v, u, tar);
10.                 }
11. }
13. dfs(1, 0, p);
14. dis[p] = 0;
15. dfs(p, 0, q);

复制代码

2、树型DP求树的直径
优点：可以求出以当前节点为根时的最长链，支持边为负权，时间复杂度O(N)。
缺点：不能求出最长链的路径。
方法：对于每个节点我们要记录两个值：
\(f_{1_i}\) 表示以i为根的子树中，i到叶子结点距离的最大值
\(f_{2_i}\) 表示以i为根的子树中，i到叶子结点距离的次大值
对于一个节点，它到叶子结点距离的最大值和次大致所经过的路径肯定是不一样的
若j是i的儿子，那么（下面的 \(w_{i,j}\) 表示i到j的路径长度）：
（1）若 \(f_{1_i}\) < \(f_{1_j}\) + \(w_{i,j}\) ， \(f_{2_i}\) = \(f_{1_i}\) ， \(f_{1_i}\) = \(f_{1_j}\) + \(w_{i,j}\) ；
（2）否则，若 \(f_{2_i}\) < \(f_{1_j}\) + \(w_{i,j}\) ， \(f_{2_i}\) = \(f_{1_j}\) + \(w_{i,j}\) ；
理解：这样做就是，先看能否更新最大值，若能，它的次大值就是原先的最大值，再更新它的最大值；若不能，就看能不能更新次大值，若能，就更新，不能就不管它
这样的话，最后的答案 \(ans = max\) {\(f_{1_i} + f_{2_i}\)}
代码：

1. inline void dp(int u, int fa)            
2. {
3.     int v;
4.           for(int e = hd[u]; e; e = nt[e])     
5.                   if((v = to[e]) ^ fa)
6.                 {   
7.                     dp(v, u);                  
8.                     if(f1[u] < f1[v] + w[e])      
9.                     {
10.                               f2[u] = f1[u];            
11.                               f1[u] = f1[v] + w[e];        
12.                     }         
13.                     else if(f2[u] < f1[v] + w[e])   
14.                     f2[u] = f1[v] + w[e];
15.                         //依次更新最大、次大，不能就不管它
16.                     ans = max(ans, f1[u] + f2[u]);   
17.                   }
18. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4