Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- #include <stack>
- #include <queue>
- #include <algorithm>
- #include <cmath>
- #include <set>
- #include <map>
- using namespace std;
- vector<int> g[223456];
- int dist[223456];
- int dist2[223456];
- void dfs(int v, int p = -1)
- {
- for(int i = 0; i < g[v].size(); ++i)
- {
- int to = g[v][i];
- if (to == p)
- continue;
- dfs(to, v);
- }
- }
- void dfsWithDist(int v, int p = -1)
- {
- for(int i = 0; i < g[v].size(); ++i)
- {
- int to = g[v][i];
- if (to == p)
- continue;
- dist[to] = dist[v] + 1;
- dfsWithDist(to, v);
- }
- }
- void dfsWithDist2(int v, int p = -1)
- {
- for(int i = 0; i < g[v].size(); ++i)
- {
- int to = g[v][i];
- if (to == p)
- continue;
- dist2[to] = dist2[v] + 1;
- dfsWithDist2(to, v);
- }
- }
- bool dfsWithPath(int v, int u, vector<int>& path, int p = -1)
- {
- path.push_back(v);
- if (v == u)
- return true;
- for(int i = 0; i < g[v].size(); ++i)
- {
- int to = g[v][i];
- if (to == p)
- continue;
- if (dfsWithPath(to, u, path, v))
- return true;
- }
- path.pop_back();
- }
- bool used[223456];
- int distLast[223456];
- int mx;
- void dfsWithUsedAndDist(int v)
- {
- used[v] = 1;
- for(int i = 0; i < g[v].size(); ++i)
- {
- int to = g[v][i];
- if (used[to])
- continue;
- distLast[to] = distLast[v] + 1;
- mx = max(mx, distLast[to]);
- dfsWithUsedAndDist(to);
- }
- }
- int longestPath[223456];
- bool ok(vector<int>&path, int d, int m) {
- int l = m;
- int r = d - m - 1;
- if ((r-l) / 2 > m)
- return false;
- for(int i = 0; i < path.size(); ++i) {
- int mn = 1e9;
- mn = min(mn, longestPath[path[i]] + abs(l-i));
- mn = min(mn, longestPath[path[i]] + abs(r-i));
- if (mn > m)
- return false;
- }
- return true;
- }
- int main()
- {
- int n;
- cin >> n;
- for(int i = 0; i < n-1; ++i)
- {
- int u, v;
- cin >> u >> v;
- g[v].push_back(u);
- g[u].push_back(v);
- }
- dfsWithDist(1);
- int ind = max_element(dist + 1, dist + n + 1) - dist;
- dfsWithDist2(ind);
- int ind2 = max_element(dist2 + 1, dist2 + n + 1) - dist2;
- vector<int> path;
- dfsWithPath(ind, ind2, path);
- // for(int i = 0; i < path.size(); ++i)
- // cout << path[i] << " ";
- // cout << endl;
- int d = path.size();
- for(int i = 0; i < path.size(); ++i)
- used[path[i]] = 1;
- for(int i = 0; i < path.size(); ++i) {
- mx = 0;
- dfsWithUsedAndDist(path[i]);
- longestPath[path[i]] = mx;
- }
- for(int i = 1; i <= n; ++i)
- used[i] = 0;
- for(int i = 0; i < path.size(); ++i)
- used[path[i]] = 1;
- int l = 0;
- int r = d / 2 + 1;
- while(r-l > 1)
- {
- int m = (l+r) >> 1;
- if (ok(path, d, m))
- r = m;
- else
- l = m;
- }
- if (ok(path, d, l))
- r = l;
- if (r == d-r-1)
- cout << path[r] << " " << path[d-r] << endl;
- else
- cout << path[r] << " " << path[d-r-1] << endl;
- // int l,r;
- // int mxL = ((d & 1) ? d / 4 : (d-1) / 4);
- // int mxR = d-1 - mxL;
- //
- // if (d&1) {
- // mxL = max(mxL, longestPath[path[d/2]]);
- // mxR = min(mxR, d-1 - longestPath[path[r]]);
- // --l, ++r;
- // if (longestPath[path[d/2]] == d/2) {
- // cout << path[d/2] << " " << (path[d/2] == 1 ? 2 : 1) << endl;
- // return 0;
- // }
- // l = d/2 - 1;
- // r = d/2 + 1;
- // }
- // else {
- // l = d/2 - 1;
- // r = d/2;
- // }
- // while(l >= 0) {
- // if (d & 1) {
- // mxL = max(mxL, longestPath[path[l]] + l - d/2);
- // mxR = min(mxR, d/2 + r - longestPath[path[r]]);
- // } else {
- // mxL = max(mxL, longestPath[path[l]] + l - d/2 + 1);
- // mxR = min(mxR, d/2 + r - longestPath[path[r]] - 1);
- // }
- // --l, ++r;
- // }
- // cout << path[mxL] << " " << path[mxR] << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement