题解 P3304 【[SDOI2013]直径】
Toheart
2017-08-28 22:15:44
#洛谷首题解！
##第一问：裸求树的直径，跑两遍DFS/DFS/树形DP，原理请百度。
##第二问：易知答案边一定在开始求的直径上，易知将所有的直径覆盖在一起形似一个两边有分叉的树干，所以要缩小左右端点的范围。具体要遍历直径，并判断每个点是否为两直径交点，若是则将分叉的点舍弃掉。
···
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn = 200010;
int n, tot, far;
long long maxd;
int st[maxn], fa[maxn];
long long dis[maxn];
bool isol[maxn];
struct node{
int v, w, nxt;
} edge[2*maxn];
inline void in(int x, int y, int z){
edge[++tot].v = y;
edge[tot].w = z;
edge[tot].nxt = st[x];
st[x] = tot;
}
void DFS(int now, int f){
fa[now] = f;
if(maxd < dis[now]){
far = now;
maxd = dis[now];
}
for(int i = st[now]; i; i = edge[i].nxt){
int to = edge[i].v;
if(to != f){
dis[to] = dis[now] + edge[i].w;
DFS(to, now);
}
}
}
void Liuhaoyu(int now, int f){
if(maxd < dis[now]) maxd = dis[now];
for(int i = st[now]; i; i = edge[i].nxt){
int to = edge[i].v;
if(to != f && !isol[to]){
dis[to] = dis[now] + edge[i].w;
Liuhaoyu(to, now);
}
}
}
int main(){
scanf("%d", &n);
for(int i = 1, x, y, z; i < n; i++){
scanf("%d%d%d", &x, &y, &z);
in(x, y, z);
in(y, x, z);
}
DFS(1, 0);
//printf("%d\n", far);
int op = far;
maxd = dis[op] = 0;
//memset(fa, 0, sizeof(fa));
DFS(op, 0);
//printf("%d\n", far);
/*for(int i = 1; i <= n; i++)
printf("%d ", dis[i]);*/
printf("%lld\n", maxd);
for(int i = far; i; i = fa[i])
isol[i] = 1;
int l = op, r = far;
bool flag = 0;
for(int i = fa[far]; i != op; i = fa[i]){
int ld = dis[i];
int rd = dis[far] - dis[i];
maxd = dis[i] = 0;
Liuhaoyu(i, 0);
if(maxd == ld && !flag){
l = i;
flag = 1;
```
}//左端点只能缩一次，因为点从右端遍历过来，若再改变左端点范围会扩大。
```cpp
if(maxd == rd) r = i;
}
long long ans = 0;
for(int i = r; i != l; i = fa[i])//注意是边，所以少一个
ans++;
printf("%lld\n", ans);
return 0;
}
···
```