fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  3. #define ll long long
  4. #define ld long double
  5. #define pb push_back
  6. using namespace std;
  7. int mx=-1,to;
  8. vector<vector<int>>v;
  9. const int m=2e5+1;
  10. int vis[m],src,dist;
  11. vector<int>dia;
  12. bool in_path[m];
  13. void dfs(int node,int cost)
  14. {
  15.     if(cost>mx)
  16.     {
  17.         mx=cost;
  18.         to=node;
  19.     }
  20.     vis[node]=1;
  21.     for(auto child:v[node])
  22.     {
  23.         if(!vis[child])
  24.         {
  25.             dfs(child,cost+1);
  26.         }
  27.     }
  28. }
  29. int ans=0;
  30. void dfs2(int node)
  31. {
  32.     vis[node]=1;
  33.     dia.pb(node);
  34.     if(node==dist)
  35.     {
  36.         for(auto i:dia) in_path[i]=1;
  37.         ans=dia.size();
  38.         return;
  39.     }
  40.     for(auto child:v[node])
  41.     {
  42.         if(!vis[child])
  43.             {dfs2(child);
  44.             dia.erase(dia.end()-1);
  45.             }
  46.     }
  47. }
  48. int mxdepth=0,mxind=-1;
  49. void dfs3(int node,int depth)
  50. {
  51.     vis[node]=1;
  52.     if(v[node].size()==1&&node!=dist&&node!=src)
  53.     {
  54.          if(depth>mxdepth)
  55.          {
  56.           mxdepth=depth;
  57.           mxind=node;
  58.          }
  59.     }
  60.     for(auto child:v[node])
  61.     {
  62.         if(!vis[child])
  63.         {
  64.             if(in_path[child])
  65.             {
  66.                 dfs3(child,0);
  67.             }
  68.             else dfs3(child,depth+1);
  69.         }
  70.     }
  71. }
  72. int main(){
  73. fast;
  74. int n;
  75. cin>>n;
  76. v.resize(n+1);
  77. for(int i=0;i<n-1;i++)
  78. {
  79.     int a,b;
  80.     cin>>a>>b;
  81.     v[a].pb(b);
  82.     v[b].pb(a);
  83. }
  84. dfs(1,0);
  85.  src=to;
  86. memset(vis,0,sizeof vis);
  87. mx=-1;
  88. dfs(to,0);
  89. dist=to;
  90. memset(vis,0,sizeof vis);
  91. dfs2(src);
  92. memset(vis,0,sizeof vis);
  93. dfs3(src,0);
  94. ans--;
  95. if(mxdepth==0)
  96. {
  97.         for(int i=1; i<=n; i++)
  98.         {
  99.             if(in_path[i]&&i!=dist&&i!=src)
  100.             {
  101.                 mxind=i;
  102.                 break;
  103.             }
  104.         }
  105. }
  106. ans+=mxdepth;
  107. cout<<ans<<endl;
  108. cout<<src<<" "<<dist<<" "<<mxind<<endl;
  109.     return 0 ;
  110. }
Runtime error #stdin #stdout 0.01s 5476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Aw1wgD
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!