知名高端网站建设,舞蹈网站模版,wordpress菜单排序,宣传册设计及网站建设W 市的交通规划出现了重大问题#xff0c;市政府下定决心在全市各大交通路口安排疏导员来疏导密集的车流。 但由于人员不足#xff0c;W 市市长决定只在最需要安排人员的路口安排人员。 具体来说#xff0c;W 市的交通网络十分简单#xff0c;由 n 个交叉路口和 n−1 条街道… W 市的交通规划出现了重大问题市政府下定决心在全市各大交通路口安排疏导员来疏导密集的车流。 但由于人员不足W 市市长决定只在最需要安排人员的路口安排人员。 具体来说W 市的交通网络十分简单由 n 个交叉路口和 n−1 条街道构成交叉路口路口编号依次为 0,1,…,n−1 。 任意一条街道连接两个交叉路口且任意两个交叉路口间都存在一条路径互相连接。 经过长期调查结果显示如果一个交叉路口位于 W 市交通网最长路径上那么这个路口必定拥挤不堪。 所谓最长路径定义为某条路径 p(v1,v2,…,vk)路径经过的路口各不相同且城市中不存在长度大于 k 的路径因此最长路径可能不唯一。 因此 W 市市长想知道哪些路口位于城市交通网的最长路径上。 输入格式 第一行包含一个整数 n 之后 n−1行每行两个整数 u,v表示编号为 u和 v 的路口间存在着一条街道。 输出格式 输出包括若干行每行包括一个整数——某个位于最长路径上的路口编号。 为了确保解唯一请将所有最长路径上的路口编号按编号顺序由小到大依次输出。 数据范围 1≤n≤2×105 输入样例 10
0 1
0 2
0 4
0 6
0 7
1 3
2 5
4 8
6 9输出样例 0
1
2
3
4
5
6
8
9两次dfs第一次求树的直径和当前点向下的最大值和次大值,第二次求当前点向上的最大值 #include iostream
#include cstring
#include algorithm
using namespace std;
constexpr int N1e67;
int n,d1[N],d2[N],p[N],up[N];
int h[N],e[N],ne[N],idx;
int maxd;
void add(int a,int b){e[idx]b;ne[idx]h[a];h[a]idx;
}
void dfs_d(int u,int f){for(int ih[u];i!-1;ine[i]) {int j e[i];if (j ! f) {dfs_d(j, u);int dis d1[j] 1;if (dis d1[u]) {d2[u] d1[u], d1[u] dis;p[u] j;} else if (dis d2[u]) {d2[u] dis;}}}maxd max(maxd,d1[u]d2[u]);
}
void dfs_u(int u,int f){for(int ih[u];i!-1;ine[i]) {int j e[i];if (j ! f) {up[j]up[u]1;if(p[u]j) up[j] max(up[j],d2[u]1);else up[j] max(up[j],d1[u]1);dfs_u(j,u);}}
}
int main(){memset(h,-1,sizeof h);scanf(%d,n);for(int i1;in;i){int a,b;scanf(%d%d,a,b);add(a,b),add(b,a);}dfs_d(0,-1);dfs_u(0,-1);for (int i 0; i n; i){int a[3] {up[i], d1[i], d2[i]};sort(a, a 3);if (a[1] a[2] maxd){printf(%d\n,i);}}return 0;
}
