LOJ10159旅游规划

W 市的交通规划出现了重大问题，市政府下定决心在全市各大交通路口安排疏导员来疏导密集的车流。但由于人员不足，W 市市长决定只在最需要安排人员的路口安排人员。

具体来说，W 市的交通网络十分简单，由

经过长期调查，结果显示，如果一个交叉路口位于 W 市交通网最长路径上，那么这个路口必定拥挤不堪。所谓最长路径，定义为某条路径

第一行一个整数

之后

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

样例输入

样例输出

对于全部数据， $1≤n≤2×10^5。$

$_____________________________________________________________________________________________________________$

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=2e5+10;
 4 int n;
 5 struct edge
 6 {
 7     int u,v,nxt;
 8 }e[maxn<<1];
 9 int head[maxn],js;
10 void addage(int u,int v)
11 {
12     e[++js].u=u;e[js].v=v;
13     e[js].nxt=head[u];head[u]=js;
14 }
15 int ml[maxn],sl[maxn];
16 int ans=0;
17 void dp(int u,int fa)
18 {
19     for(int i=head[u];i!=-1;i=e[i].nxt)
20     {
21         int v=e[i].v;
22         if(v!=fa)
23         {
24             dp(v,u);
25             if(ml[v]+1>ml[u])
26             {
27                 sl[u]=ml[u];
28                 ml[u]=ml[v]+1;
29             }
30             else if(ml[v]+1>sl[u])
31                 sl[u]=ml[v]+1;
32         }
33     }
34     if(ml[u]+sl[u]>ans)ans=ml[u]+sl[u];
35 }
36 int q[maxn],jss,bz[maxn];
37 void work(int u,int fa,int len)
38 {
39     if(bz[u]==0)
40     {
41         q[jss++]=u;
42         bz[u]=1;
43     }
44     for(int i=head[u];i!=-1;i=e[i].nxt)
45     {
46         int v=e[i].v;
47         if(v!=fa)
48         {
49             if(ml[v]==len-1)work(v,u,len-1);
50         }
51     }
52 }
53 void dfs(int u,int fa)
54 {
55     if(ml[u]+sl[u]==ans)
56     {
57         if(ml[u]!=sl[u])work(u,fa,ml[u]);
58         work(u,fa,sl[u]);
59     }
60     for(int i=head[u];i!=-1;i=e[i].nxt)
61     {
62         int v=e[i].v;
63         if(v!=fa)dfs(v,u);
64     }
65 }
66 int main()
67 {
68     scanf("%d",&n);
69     memset(head,-1,sizeof(head));
70     for(int u,v,i=1;i<n;++i)
71     {
72         scanf("%d%d",&u,&v);
73         addage(u,v);addage(v,u);
74     }
75     dp(0,-1);
76     dfs(0,-1);
77     sort(q,q+jss);
78     for(int i=0;i<jss;++i)printf("%d
",q[i]);
79     return 0;
80 }

LOJ10159旅游规划

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示