树的直径

两次bfs即可

问题

给定一棵树,求最远的两点之间的距离。
两次bfs就行了,具体的证明有一点麻烦

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int n;
int d[maxn];
bool vis[maxn];
struct Edge{
int v, weight;
};
vector<Edge> G[maxn];
int bfs(int u){
for(int i=0; i<n; i++) d[i] = -1;
memset(vis, 0, sizeof(vis));
d[u] = 0;
queue<int> q;
q.push(u);
vis[u] = true;
int long_dis = -1;
while(!q.empty()){
int temp = q.front();
q.pop();
for(int i=0; i<G[temp].size(); i++){
Edge e = G[temp][i];
if(vis[e.v]) continue;
else{
if(d[e.v]<d[temp]+e.weight){
d[e.v]=d[temp]+e.weight;
q.push(e.v);
long_dis = e.v;
vis[e.v] = true;
}
}
}
}
return long_dis;
}
void solve(){
int p = bfs(0);
int q = bfs(p);
int ans = -1;
for(int i=0; i<n; i++){
ans = max(ans, d[i]);
}
printf("%d\n", ans);
}
int main()
{
while(cin>>n){
int u, v, weight;
for(int i=0; i<n-1; i++){
cin>>u>>v>>weight;
G[u].push_back(Edge{v, weight});
G[v].push_back(Edge{u, weight});
}
solve();
}
return 0;
}

未解决的问题

文章目录
  1. 1. 问题
    1. 1.1. 代码
  2. 2. 未解决的问题
{{ live2d() }}