Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- typedef long long ll;
- using namespace std;
- const int MX = 1e5 + 69;
- int dis[MX];
- multiset<int> nigga;
- vector<int> adj[MX];
- int bfs(int root)
- {
- nigga.clear();
- memset(dis,-1,sizeof dis);
- queue<int> q;
- q.push(root);
- dis[root] =0;
- int mx =-1,opt=1e9+6;
- while(!q.empty())
- {
- int nxt = q.front();
- q.pop();
- for(auto u :adj[nxt])
- {
- if(dis[u]!=-1)continue;
- dis[u] = dis[nxt] +1;
- if(dis[u]>mx)
- {
- mx = dis[u];
- opt = u;
- }
- if(u!=root&&adj[u].size()==1)
- nigga.insert(dis[u]);
- q.push(u);
- }
- }
- return opt;
- }
- int main()
- {
- int n;
- cin>>n;
- if(n==1)
- {
- cout<<0;return 0;
- }
- for(int i=1;i<n;i++)
- {
- int a,b;
- scanf("%d%d",&a,&b);
- adj[a].push_back(b);
- adj[b].push_back(a);
- }
- int uu = bfs(bfs(1));
- auto u = nigga.end();
- u--;
- int ans = *u;
- if(u!=nigga.begin())
- {
- u--;
- ans -= *u;
- }
- bfs(uu);
- u = nigga.end();
- u--;
- int res = *u;
- if(u!=nigga.begin())
- {
- u--;
- res -= *u;
- }
- if(ans+res>=n)ans=max(ans,res);
- else ans =res + ans;
- cout<<ans<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement