Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 100005;
- #define ii pair<int, int>
- #define fi first
- #define sc second
- vector<int> a[N];
- int vis[N];
- int mx = 0, l, r;
- ii dfs(int i) {
- vis[i] = 1;
- vector<ii> v;
- for (auto j : a[i]) if (!vis[j]) {
- v.push_back(dfs(j));
- }
- if (v.size() == 0) return ii(0, i);
- else if (v.size() == 1) {
- if (v[0].fi + 1 > mx) {
- mx = v[0].fi + 1;
- l = v[0].sc; r = i;
- }
- }
- else {
- sort(v.begin(), v.end(), greater<ii>());
- if (v[0].fi + v[1].fi + 1 > mx) {
- mx = v[0].fi + v[1].fi + 1;
- l = v[0].sc; r = v[1].sc;
- }
- }
- return ii(v[0].fi + 1, v[0].sc);
- }
- int main() {
- //freopen("in", "r", stdin);
- int n; cin >> n;
- for (int i = 1; i < n; i++) {
- int u, v; cin >> u >> v;
- a[u].push_back(v);
- a[v].push_back(u);
- }
- l = r = 1; dfs(1);
- cout << l << ' ' << r << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement