Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define N 100005
- vector<int> a[N];
- int dis[N];
- int ans[N];
- bool vis[N];
- void fun(int node) {
- vis[node] = 1;
- dis[node] = N;
- for(auto i : a[node]) {
- if(!vis[i]) {
- fun(i);
- dis[node] = min(dis[i] + 1, dis[node]);
- }
- }
- if(dis[node] == N) {
- dis[node] = 1;
- }
- }
- void fun2(int node, int pre) {
- // cout << node << " - " << pre << endl;
- vis[node] = 1;
- vector<pair<int,int>> tmp;
- if(node != 1 || a[node].size() == 1) {
- tmp.push_back({pre, -1});
- }
- bool f = 0;
- for(auto i : a[node]) {
- if(!vis[i]) {
- tmp.push_back({dis[i], i});
- f = 1;
- }
- }
- if(!f) {
- tmp.push_back({0,-2});
- }
- sort(tmp.begin(),tmp.end());
- auto calc = [&] (vector<int> vvv) {
- set<int> st;
- for(auto i : vvv) {
- st.insert(i);
- }
- for(auto i : tmp) {
- if(st.find(i.second) == st.end()) {
- return i.first;
- }
- }
- return 0;
- };
- for(auto i : a[node]) {
- if(!vis[i]) {
- fun2(i, calc({i}) + 1);
- }
- }
- ans[node] = tmp[0].first + 1;
- }
- void solve()
- {
- int n, x, y;
- cin >> n;
- for(int i = 0; i < n - 1; i++) {
- cin >> x >> y;
- a[x].push_back(y);
- a[y].push_back(x);
- }
- fun(1);
- memset(vis, false, sizeof(bool) * (n + 1));
- fun2(1, 0);
- int mx = -1, ps = 0;
- for(int i = 1; i <= n; i++) {
- if(ans[i] > mx) {
- mx = ans[i];
- ps = i;
- }
- }
- // for(int i = 1; i <= n; i++) {
- // cout << i << " -> " << dis[i] << " " << ans[i] << endl;
- // }
- cout << ps << " " << mx << endl;
- return;
- }
- int main()
- {
- int TESTS=1;
- // cin>>TESTS;
- while(TESTS--)
- {
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment