中国机械工业建设集团有限公司网站/百度贴吧网页版入口

# 旅游规划

## 题目描述

W市的交通规划出现了重大问题，市政府下定决心在全市各大交通路口安排疏导员来疏导密集的车流。但由于人员不足，W市市长决定只在最需要安排人员的路口安排人员。  
具体来说，W市的交通网络十分简单，由n个交叉路口和n−1条街道构成，交叉路口路口编号依次为0,1,…,n−1。任意一条街道连接两个交叉路口，且任意两个交叉路口间都存在一条路径互相连接。  
经过长期调查，结果显示，如果一个交叉路口位于W市交通网最长路径上，那么这个路口必定拥挤不堪。所谓最长路径，定义为某条路径p=（v1,v2,v3,⋯,vk），路径经过的路口各不相同，且城市中不存在长度大于k的路径，因此最长路径可能不唯一。因此W市市长想知道哪些路口位于城市交通网的最长路径上。

## 输入格式

第一行一个整数n；  
之后n−1行每行两个整数u,v，表示u和v的路口间存在着一条街道。

## 输出格式

输出包括若干行，每行包括一个整数表示某个位于最长路径上的路口编号。  
为了确保解唯一，请将所有最长路径上的路口编号按编号顺序由小到大依次输出。

## 样例 #1

### 样例输入 #1

```
10
0 1
0 2
0 4
0 6
0 7
1 3
2 5
4 8
6 9
```

### 样例输出 #1

```
0
1
2
3
4
5
6
8
9
```

## 提示

1≤n≤2×10^5。

核心思路

注意到，向上最长链+向下最长链 = 直径 之时 ，点在直径上

AC 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 114514;
int n;
int fix(int x){int s = 0;for(int i = 2;i <= sqrt(x);i++){if(x%i == 0){s += i;//	cout<<i<<endl;if(i != x/i){s += x/i;}if(s > x){return 11451419;}}}return s+1;
}
vector<int> g[500010];
int d1[500010],d2[500010],up[500010],ans;
bool tag[500010];
void dfs(int u,int fa) {
//	cout<<u<<endl;for (int v:g[u]) {if(v == fa)continue;dfs(v,u);int tot = d1[v] + 1;if (tot > d1[u]) {d2[u] = d1[u];d1[u] = tot;} else {d2[u] = max(d2[u], tot);}}ans= max(ans, d1[u] + d2[u]);return;
}void ys(int u,int fa) {for (int v:g[u])  {if(v == fa)continue;up[v] = max(up[u],(d1[u] == d1[v]+1?d2[u]:d1[u])) +1; ys(v,u);}return;
}
int main(){int n;cin>>n;for(int i = 1;i <= n-1;i++){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}dfs(0,-1);ys(0,-1);for (int i = 0; i < n; i++) {if (d1[i] + max(d2[i], up[i]) == ans) {printf("%d\n", i);}}return 0;
}