直径
59percent
2019-07-27 19:16:29
```cpp
/*
直径： 正权求法两次dfs：
1. 任意选一个点做为根，找最长的一个点p1
2. 用p1做根，找最长一个点q, p1->q就是一条直径
2.1 p1做根，找出所有最长的点qi，
2.2 p1 -> qi都是直径，找出p1->qi的公共LCA, lcaq
2.3 任意选一个q1，找出所有最长的点pi
lcap lcaq
p1 ---- Y-----X-----> q1
p2 ----| |____> q2
|-- q3
3. dep[lcaq] - dep[lcap] -> 边的数目
*/
```
# 朴素算法
```cpp
#include <iostream>
#include <vector>
#define N 200005
using namespace std;
typedef long long ll;
struct Edge {
int y, w;
};
vector<Edge> g[N];
int n, fa[N], dep[N];
ll len[N], mx = 0;
int p[N], last;
void getMaxs() {
last = 0;
mx = 0;
for (int i = 1; i <= n; i++)
mx = max(mx, len[i]);
for (int i = 1; i <= n; i++)
if (len[i] == mx)
p[++last] = i;
}
void dfs(int x, int _fa, int _dep, ll _len) {
fa[x] = _fa;
dep[x] = _dep;
len[x] = _len;
for (int i = 0; i < g[x].size(); i++) {
int y = g[x][i].y, w = g[x][i].w;
if (y == _fa) continue;
dfs(y, x, _dep + 1, _len + w);
}
}
int lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
while (dep[x] > dep[y])
x = fa[x];
while (x != y) {
x = fa[x];
y = fa[y];
}
return x;
}
int getCommonLca() {
int x = p[1];
for (int i = 2; i <= last; i++)
x = lca(x, p[i]);
return x;
}
int main() {
cin >> n;
for (int i = 1; i <= n - 1; i++) {
int x, y, w;
cin >> x >> y >> w;
Edge e1 = {y, w};
g[x].push_back(e1);
Edge e2 = {x, w};
g[y].push_back(e2);
}
dfs(1, 0, 1, 0);
getMaxs();
dfs(p[1], 0, 1, 0);
getMaxs();
int lca_u = getCommonLca();
dfs(p[1], 0, 1, 0);
getMaxs();
int lca_v = getCommonLca();
cout << mx << endl;
cout << (dep[lca_v] - dep[lca_u]) << endl;
return 0;
}
```
# 正解
```cpp
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
struct Edge {
int y, w;
};
const int N=200005;
int n,dep[N],fa[N], lgn, st[N][18];
ll dis[N], mx;
int p[N], last;
vector<Edge> g[N];
void calcMaxs() {
last = 0, mx=0;
for(int i=1; i<=n; i++)
mx = max(mx, dis[i]);
for(int i=1; i<=n; i++)
if(dis[i]==mx)
p[++last] = i;
}
void dfs(int x, int _fa, int _dep, ll _dis) {
fa[x] = _fa;
dep[x] = _dep;
dis[x] = _dis;
st[x][0] = _fa;
for(int i=0; i<g[x].size(); i++) {
int y = g[x][i].y, w=g[x][i].w;
if(y == _fa) continue;
dfs(y, x, _dep+1, _dis+w);
}
}
void initSt() {
for(int j=1; j<=lgn; j++)
for(int i=1; i<=n; i++)
st[i][j] = st[st[i][j-1]][j-1];
}
int lca(int x, int y) {
if(dep[x]<dep[y]) swap(x, y);
/*while(dep[x]>dep[y])
x = fa[x];
while(x!=y) {
x = fa[x];
y = fa[y];
}*/
int d = dep[x] - dep[y];
for(int i=0; i<=lgn; i++)
if((d>>i)&1)
x = st[x][i];
if(x==y) return x;
for(int i=lgn; i>=0; i--) {
if(st[x][i]==st[y][i]) continue;
x = st[x][i];
y = st[y][i];
}
return st[x][0];
}
int commonLca() {
int cl = p[1];
for(int i=2; i<=last; i++)
cl = lca(cl, p[i]);
return cl;
}
int main() {
cin>>n;
lgn = log2(n);
for(int i=1; i<=n-1; i++) {
int x, y, w;
cin>>x>>y>>w;
g[x].push_back((Edge){y, w});
g[y].push_back((Edge){x, w});
}
//第一个端点u
dfs(1, 0, 1, 0);
calcMaxs();
int u = p[1];
//第二个端点v
dfs(u, 0, 1, 0);
calcMaxs();
int v = p[1];
//u为根的时候，p[i]的公共lca
initSt();
int lca_u = commonLca();
//v为根的时候，p[i]的公共lca
dfs(v, 0, 1, 0);
calcMaxs();
initSt();
int lca_v = commonLca();
//求公共边的数目, dep[lca_v]-dep[lca_u]
cout<<mx<<endl;
cout<<dep[lca_v]-dep[lca_u]<<endl;
return 0;
}
```