问题描述
给定一棵树,树中每条边都有一个权值,树中两点之间的距离定义为连接两点的路径边权之和。树中最远的两个节点(两个节点肯定都是叶子节点)之间的距离被称为树的直径,连接这两点的路径被称为树的最长链。后者通常也可称为直径。
算法：
不妨设1号节点为根，“N个节点，N-1条边的无向图”就可以看作“有根树”。设d[x]表示从节点x出发走向以x为根的子树，能够到达最远节点的距离。设x的子节点为y1，y2，……，yt，edge(x, y)表示边权，显然有：
d[x] = max{d[yi] + edge(x, yi)} (1≤i≤t)
接下来，我们可以考虑对每个节点x求出“经过节点x的最长链的长度”ans[x],整棵树的直径就是：
max{ans[x]} (1≤x≤n)
那么，如何求ans[x]呢？我们用链式前向星存图，依次遍历以x为起点的所有连边，用已经更新过的d[x]与没有枚举到的x的连边之和来更新ans[x]:
ans[x] = max(ans[x], d[x] + d[yi] + edge(x, yi))
然后再不断更新
d[x] = max(d[x], d[yi] + edge(x, yi))
注意ans[i]存的是经过i节点的最长链，最后还要便利一遍ans才能求到真正的直径 而我们的ans数组其实可以用一个整型数ans代替，就不需要后面再更新一遍了
ans = max(ans, d[x] + d[yi] + edge(x, yi))
关键代码：
void dp(int x
){
vis
[x
]=1;
for(int i
=head
[x
];i
;i
=edge
[i
].next
){
int y
=edge
[i
].to
;
if(vis
[y
]) continue;
dp(y
);
ans
=max(ans
,d
[x
]+d
[y
]+edge
[i
].dis
);
d
[x
]=max(d
[x
],d
[y
]+edge
[i
].dis
);
}
}
拓展：两次DFS求直径
算法
在树上任选一节点
u
u
u ，通过搜索求得距离它最远的点
x
x
x ，再从点
x
x
x 出发通过搜索得到距离它最远的点
y
y
y ，
x
x
x 到
y
y
y 的路径即为这棵树的直径。
代码
#include<cstdio>
#include<iostream>
#include<vector>
using namespace std
;
const int MAXN
=100005;
vector
<int> g
[MAXN
];
int point
,maxn
;
void dfs(int now
,int fa
,int step
){
if(step
>maxn
){
maxn
=step
;
point
=now
;
}
for(int i
=0;i
<g
[now
].size();i
++){
int v
=g
[now
][i
];
if(v
!=fa
){
dfs(v
,now
,step
+1);
}
}
}
int main(){
int n
;
scanf("%d",&n
);
for(int i
=1;i
<=n
-1;i
++){
int u
,v
;
scanf("%d %d",&u
,&v
);
g
[u
].push_back(v
);
g
[v
].push_back(u
);
}
maxn
=-1;
dfs(1,0,0);
maxn
=-1;
dfs(point
,0,0);
printf("%d",maxn
);
return 0;
}
