描述
W市的交通规划出现了重大问题，市*下决心在全市的各大交通路口安排交通疏导员来疏导密集的车流。但由于人员不足，W市市长决定只在最需要安排人员的路口安放人员。具体说来，W市的交通网络十分简单，它包括n个交叉路口和n-1条街道，任意一条街道连接两个交叉路口，并且任意两个交叉路口之间都存在一条路径互相连接。经过长期调查结果显示如果一个交叉路口位于W市交通网的最长路径上，那么这个路口必然拥挤不堪，所谓最长路径定义为某条路径p=(v1,v2,v3…vk)，路径经过的路口各不相同且城市中不存在长度>k的路径（因此可能存在着不唯一的最长路径）。因此W市市长希望知道有哪些路口位于城市交通网的最长路径之上。
格式
输入格式
第一行包括一个整数n。
之后的n-1行每行包括两个整数u, v表示编号为u和v的路口之间存在着一条街道（注意：路口被依次编号为0到n-1）
输出格式
输出包括若干行，每行包括一个整数——某个位于最长路上路口的编号。
为了确保解唯一，我们规定位于所有最长路上的路口按编号顺序从小到大输出。
提示
这里存在着若干条最长路径，其中的两条是3-1-0-2-5与8-4-0-6-9，他们的长度都是5，但是不存在长度>5的路径且所有最长路径都不包括路口7，所以答案中没有7。
数据范围：
对于50%的数据保证n<=1000
对于100%的数据保证n<=200000
-----------------------------------------------------------------------
当然是先求树的直径，用dfs或dp
这里用dp比较方便，f[i][0]最长f[i][1]次长，初始化-1代表没计算过,计算时先f[i][0]=0，f[i][1]可以等于-1（没有第二个孩子）
注意更新最大时要先把最大赋给次大
然后是统计那些点在直径上
我一开始想了一个方法，先找到一个在直径上的点，然后对于他dfs所有f[v][0]==f[root][0]-1||f[v][0]==f[root][1]-1的v，其他的只dfs f[v][0]==f[u][0]-1的；感觉所有直径经过同一点，应该没问题，可是一直90，即使考虑不经过同一点成了80
［2016.9.6: 应该找中点］
正解依然是DP，这次从上到下，先算父亲再算孩子，g[i]表示i向子树外最远距离，对于每个孩子j更新g[j]=1+max{g[i],max(f[k][0]+1)}，这时用dp的优越性就体现了，具体见代码
邻接表建树
PS：问路径，长度不同，把1改为w(i,j)行了，并且root别+1
//90分 自己那个方法
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int n,u,v;
struct edge{
int ne,v;
}e[N*];
int h[N],cnt=;
void ins(int u,int v){
cnt++;
e[cnt].v=v; e[cnt].ne=h[u]; h[u]=cnt;
cnt++;
e[cnt].v=u; e[cnt].ne=h[v]; h[v]=cnt;
}
int f[N][];
int dp(int u,int fa){ //cout<<u<<" u\n";
int &ans=f[u][],&ans2=f[u][];
if(ans!=-) return ans;
ans=;
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(v==fa) continue; int d=dp(v,u)+;
if(ans<d) ans2=ans,ans=d;
else if(ans2<d) ans2=d;
}
//printf("ans %d %d %d\n",u,ans,ans2);
return ans;
}
int ans[N],num=,vis[N];
void dfs(int u){//cout<<u<<" dfs\n";
if(!vis[u]) ans[++num]=u;
vis[u]=;
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(f[v][]==f[u][]-)
dfs(v);
}
}
int main(){
scanf("%d",&n);
for(int i=;i<=n-;i++) {
scanf("%d%d",&u,&v);
ins(u+,v+);
}
memset(f,-,sizeof(f));
dp(,-); int root,mx=-1e9;
for(int i=;i<=n;i++){
if(f[i][]+f[i][]+>mx){
mx=f[i][]+f[i][]+;
root=i;
}
}
ans[++num]=root; //printf("root %d %d %d\n",root,f[root][0],f[root][1]);
for(int i=h[root];i;i=e[i].ne){
int v=e[i].v;
if(f[v][]==f[root][]-||f[v][]==f[root][]-) dfs(v);
}
sort(ans+,ans++num);
for(int i=;i<=num;i++) printf("%d\n",ans[i]-);
}
//AC 正解
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int n,u,v;
struct edge{
int ne,v;
}e[N*];
int h[N],cnt=;
void ins(int u,int v){
cnt++;
e[cnt].v=v; e[cnt].ne=h[u]; h[u]=cnt;
cnt++;
e[cnt].v=u; e[cnt].ne=h[v]; h[v]=cnt;
}
int f[N][];
int dp(int u,int fa){ //cout<<u<<" u\n";
int &ans=f[u][],&ans2=f[u][];
if(ans!=-) return ans;
ans=;
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(v==fa) continue; int d=dp(v,u)+;
if(ans<d) ans2=ans,ans=d;
else if(ans2<d) ans2=d;
}
//printf("ans %d %d %d\n",u,ans,ans2);
return ans;
} int g[N];
void dp2(int u,int fa){
int cnt=;
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(v==fa) continue;
if(f[v][]==f[u][]-) cnt++;
}
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(v==fa) continue;
if(f[v][]!=f[u][]- || (f[v][]==f[u][]- && cnt>)) g[v]=max(g[u],f[u][])+;
else g[v]=max(g[u],f[u][])+;
dp2(v,u);
}
}
int ans[N],num=;
int main(){
scanf("%d",&n);
for(int i=;i<=n-;i++) {
scanf("%d%d",&u,&v);
ins(u+,v+);
}
memset(f,-,sizeof(f));
dp(,-);
dp2(,-); int mx=-1e9;
for(int i=;i<=n;i++){
if(f[i][]+f[i][]+>mx){
mx=f[i][]+f[i][]+;
}
}
for(int i=;i<=n;i++){
if(f[i][]+max(g[i],f[i][])+==mx) ans[++num]=i;
}
sort(ans+,ans++num);
for(int i=;i<=num;i++) printf("%d\n",ans[i]-); }