树的直径
一、树的直径的定义：最长的一条链。二、求法
1．两次bfs（或者dfs）求树的直径
优点：可以求出路径。
缺点：时间复杂度O(2*N)， 在负权边中无法使用。
方法：先从任意一点出发，找离它最远的点P，再从点P出发，找离它最远的点Q，P到Q的距离就是树的直径。
代码：
inline void dfs(int u, int f, int & tar)
{
int v;
for(int e = hd; e; e = nt)
if((v = to) ^ f)
{
dis = dis + w;
if(dis > dis) tar = v;
dfs(v, u, tar);
}
}
dfs(1, 0, p);
dis = 0;
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}\)}
代码：
inline void dp(int u, int fa)
{
int v;
for(int e = hd; e; e = nt)
if((v = to) ^ fa)
{
dp(v, u);
if(f1 < f1 + w)
{
f2 = f1;
f1 = f1 + w;
}
else if(f2 < f1 + w)
f2 = f1 + w;
//依次更新最大、次大，不能就不管它
ans = max(ans, f1 + f2);
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]