Это простая версия задачи. Различия между двумя версиями заключаются в ограничении на \(n\) и ограничении по времени. Делать взломы можно только в том случае, если решены обе версии задачи.
Дано дерево с \(n\) вершинами с корнем в вершине \(1\).
Для некоторой перестановки\(^\dagger\) \(a\) длины \(n\) пусть \(f(a)\) — количество пар вершин \((u, v)\) таких, что \(a_u < a_{\operatorname{lca}(u, v)} < a_v\). Здесь \(\operatorname{lca}(u,v)\) обозначает наименьшего общего предка вершин \(u\) и \(v\).
Найдите максимально возможное значение \(f(a)\) по всем перестановкам \(a\) длины \(n\).
\(^\dagger\) Перестановкой длины \(n\) является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
Примечание
Дерево в первом примере:
Одной возможной оптимальной перестановкой \(a\) является \([2, 1, 4, 5, 3]\) с \(4\)-мя подходящими парами вершин:
- \((2, 3)\), так как \(\operatorname{lca}(2, 3) = 1\) и \(1 < 2 < 4\),
- \((2, 4)\), так как \(\operatorname{lca}(2, 4) = 1\) и \(1 < 2 < 5\),
- \((2, 5)\), так как \(\operatorname{lca}(2, 5) = 1\) и \(1 < 2 < 3\),
- \((5, 4)\), так как \(\operatorname{lca}(5, 4) = 3\) и \(3 < 4 < 5\).
Дерево в третьем примере:
Дерево в четвёртом примере:
