| AIM Tech Round 4 (Div. 1) |
|---|
| Закончено |
Вам дано дерево размера n и разрешается выполнить не более 2n операций над ним. Операция заключается в выборе трех вершин x, y, y', удалении ребра (x, y) и добавлении ребра (x, y'). Операцию x, y, y' можно выполнить в случае, если выполнены все условия:
- Ребро (x, y) присутствует в дереве.
- После операции граф останется деревом.
- При удалении ребра (x, y) дерево распадается на две компоненты связности. Обозначим множество вершин в одной компоненте с вершиной x множеством Vx, а в одной компоненте с вершиной y — множеством Vy. Тогда должно выполняться условие |Vx| > |Vy|, т.е. размер компоненты с x должен быть строго больше размера компоненты с y.
Вам требуется минимизировать сумму квадратов расстояний между всеми парами вершин в итоговом дереве, полученном после не более чем 2n операций, а также предоставить последовательность операций, с помощью которых можно получить итоговое дерево из исходного.
Обратите внимание, что минимизировать количество операций не нужно. Нужно минимизировать исключительно сумму квадратов расстояний.
Первая строка входных данных содержит целое число n (1 ≤ n ≤ 2·105) — количество вершин в дереве.
Следующие n - 1 строки входных данных содержат пары целых чисел a и b (1 ≤ a, b ≤ n, a ≠ b) — описания рёбер. Гарантируется, что данные ребра образуют дерево.
В первой строке выведите число k (0 ≤ k ≤ 2n) — количество операций, которые нужно провести, чтобы минимизировать сумму квадратов расстояний между различными парами вершин.
В следующих k строках выведите по три целых числа x, y, y' — номера вершин, участвующих в очередной операции.
Операции, в которых y = y', разрешены (хоть ничего и не меняют), если выполнены условия операции.
Если возможных ответов несколько, выведите любой из них.
3
3 2
1 3
0
7
1 2
2 3
3 4
4 5
5 6
6 7
2
4 3 2
4 5 6
Иллюстрация изменений графа во втором примере из условия. Темным обозначены ребра после операции, пунктиром — до.
