1 条题解
-
0
#include<bits/stdc++.h> using namespace std; const int N=2e5+10; vector<int>G[N]; int ans,d1[N],d2[N];//d1[i]和d2[i]分别在dfs1和dfs2中有不同含义 /*dfs1中含义: d1[i]表示以点i为出发点向下的最长路径; d2[i]表示以点i为出发点向下的第二长路径; */ void dfs1(int x,int fa) { for(auto y:G[x])if(y!=fa) { dfs1(y,x); if(d1[y]+1>d1[x]) d2[x]=d1[x],d1[x]=d1[y]+1; else if(d1[y]+1>d2[x]) d2[x]=d1[y]+1; } ans=max(ans,d1[x]+d2[x]); } /*dfs2中含义: d1[i]表示以点i为出发点(可向上或向下)的最长路径; d2[i]表示以点i为出发点(可向上或向下)的第二长路径; */ void dfs2(int x,int fa) { for(auto y:G[x])if(y!=fa) { if(d1[x]!=d1[y]+1)//具有换根的意味 { if(d1[x]+1>d1[y]) d2[y]=d1[y],d1[y]=d1[x]+1; else if(d1[x]+1>d2[y]) d2[y]=d1[x]+1; }else{ if(d2[x]+1>d1[y]) d2[y]=d1[y],d1[y]=d2[x]+1; else if(d2[x]+1>d2[y]) d2[y]=d2[x]+1; } dfs2(y,x); } } int main() { int n;scanf("%d",&n); for(int i=1,x,y;i<=n-1;i++) { scanf("%d %d",&x,&y); x++,y++; G[x].push_back(y); G[y].push_back(x); } memset(d1,0,sizeof(d1)); memset(d2,0,sizeof(d2)); dfs1(1,0); dfs2(1,0); for(int i=1;i<=n;i++)if(d1[i]+d2[i]==ans) printf("%d\n",i-1); return 0; }
- 1
信息
- ID
- 1802
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 7
- 标签
- 递交数
- 23
- 已通过
- 9
- 上传者