олимпиадники-информатики

Задача №538. Три города (https://informatics.msk.ru/)
Автор разбора Кускова Юлия (9 класс, Гимназия 1 г.Витебск)

В одном государстве имеется NN городов. Некоторые города соединены дорогами, причем для любых двух городов AA и BB выполняется следующее свойство: существует ровно один способ попасть из города AA в город BB если можно перемещаться только по дорогам и не разрешается проезжать по одной и той же дороге более одного раза.

Недавно президента этой страны заинтересовал вопрос: какие три города являются наиболее удаленными друг от друга. А именно, назовем взаимной удаленностью друг от друга трех городов AA, BB и CC минимальное количество дорог, которое необходимо использовать, чтобы доехать от AA до BB, затем от BB до CC и затем от CC до AA (при этом разрешается использовать одну и ту же дорогу в различных путешествиях).

Требуется найти три города, для которых взаимная удаленность друг от друга будет максимальной.
Входные данные
В первой строке вводится число NN - количество городов (3 <= NN <= 1000). Следующие N строк содержат описания городов. Описание i-го города сначала содержит KiKi - количество городов, с которыми он соединен дорогами (1 <= KiKi < NN), а затем KiKi чисел - номера городов, с которыми он соединен. Гарантируется, что входные данные корректны - то есть если есть дорога из города A в город B, то есть и дорога из города B в город A, причем для всех пар городов выполняется свойство, указанное в условии задачи.

Выходные данные
Выведите три различных числа - номера трех наиболее удаленных друг от друга городов в произвольном порядке. Если решений несколько, выведите любое из них.
Пример
входные данные
5
1 3
1 3
3 1 2 4
2 3 5
1 4

выходные данные
5 2 1

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define pb push_back
#define F first
#define S second
#define usl unsigned long long
#define ll long long
#define ull unsigned long long
#define pll pair <int, int>
using namespace std;
const int INF = int (1e9);
vector <int> g[1002];
int dfs (int v, int pred, int &vm) { //v - текущая вершина, pred - предок, vm - вершина, которую мы считаем наиболее удаленной
	int len = 1, vd;
	vm = v;
	for (auto to : g[v])
    	if (to != pred) {
        	int pr = dfs (to, v, vd) + 1; //промежуточное значение
        	if (pr > len) {
            	len = pr;
            	vm = vd;
        	}
    	}
	return len;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#else
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif // LOCAL
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
    	int m;
    	cin >> m;
    	for (int j = 0; j < m; ++j) {
        	int a;
        	cin >> a;
        	--a;
        	g[i].push_back (a);
    	}
	}
	int len = 0, v1, v2, v3; //суммарное расстояние между вершинами, вершины - ответ на задачу
	for (int i = 0; i < n; ++i) {
    	if (g[i].size() == 1) //подвешивать дерево за листья не выгодно
        	continue;
    	pair <int, int> r [g[i].size()]; //первый элемент в паре - расстояние до наиболее удаленной вершины в поддереве, второй -  ее номер
    	for (int j = 0; j < g[i].size(); ++j)
        	r[j].first = dfs (g[i][j], i, r[j].second);
    	sort (r, r + g[i].size(), greater <pair <int, int>>()); //сортировка по невозрастанию
    	if (g[i].size() == 2) {
        	if (len < r[0].first + r[1].first) {
            	len = r[0].first + r[1].first;
            	v1 = r[0].second;
            	v2 = r[1].second;
            	v3 = i;
        	}
    	}
    	else
        	if (len < r[0].first + r[1].first + r[2].first) {
            	len = r[0].first + r[1].first + r[2].first;
            	v1 = r[0].second;
            	v2 = r[1].second;
            	v3 = r[2].second;
        	}
	}
	cout << v1 + 1 << ' ' << v2 + 1 << ' ' << v3 + 1; //ответ выводится в 1-индексации
	return 0;
}