Advertisement
jeff69

Untitled

Oct 11th, 2017
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.36 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. typedef long long ll;
  3. using namespace std;
  4. const int MX = 1e5 + 69;
  5. int dis[MX];
  6. multiset<int> nigga;
  7. vector<int> adj[MX];
  8. int bfs(int root)
  9. {
  10.     nigga.clear();
  11.     memset(dis,-1,sizeof dis);
  12.     queue<int> q;
  13.     q.push(root);
  14.     dis[root] =0;
  15.     int mx =-1,opt=1e9+6;
  16.     while(!q.empty())
  17.     {
  18.         int nxt = q.front();
  19.         q.pop();
  20.         for(auto u :adj[nxt])
  21.         {
  22.             if(dis[u]!=-1)continue;
  23.             dis[u] = dis[nxt] +1;
  24.             if(dis[u]>mx)
  25.             {
  26.                 mx = dis[u];
  27.                 opt = u;
  28.             }
  29.              if(u!=root&&adj[u].size()==1)
  30.                     nigga.insert(dis[u]);
  31.             q.push(u);
  32.         }
  33.     }
  34.     return opt;
  35. }
  36. int main()
  37. {
  38.     int n;
  39.     cin>>n;
  40.     if(n==1)
  41.     {
  42.         cout<<0;return 0;
  43.     }
  44.     for(int i=1;i<n;i++)
  45.     {
  46.         int a,b;
  47.         scanf("%d%d",&a,&b);
  48.         adj[a].push_back(b);
  49.         adj[b].push_back(a);
  50.     }
  51.     int uu = bfs(bfs(1));
  52.     auto u = nigga.end();
  53.     u--;
  54.     int ans = *u;
  55.     if(u!=nigga.begin())
  56.     {
  57.         u--;
  58.         ans -= *u;
  59.     }
  60.     bfs(uu);
  61.     u = nigga.end();
  62.     u--;
  63.     int res = *u;
  64.     if(u!=nigga.begin())
  65.     {
  66.         u--;
  67.         res -= *u;
  68.     }
  69.     if(ans+res>=n)ans=max(ans,res);
  70.     else ans =res + ans;
  71.     cout<<ans<<endl;
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement