Задача №114655. Дано дерево
За время участия в олимпиадах по информатике Влад решил множество задач о деревьях. Часто в подобных задачах в вершинах дерерва заданы некоторые объекты. Влад решал задачи, где в вершинах дерева были заданы числа, строки, правильные скобочные последовательности и даже другие деревья. Казалось, что ничего уже не может удивить Влада...
Дано дерево на \(n\) вершинах. В каждой вершине дерева задан \(k\)-мерный прямоугольный параллелепипед со сторонами, параллельными осям координат. Найдите длину кратчайшего пути такого, что пересечение параллелипипедов, соответствующих вершинам пути, пусто или сообщите, что такого пути нет.
К такому повороту событий не был готов даже повидавший многое Влад, поэтому попросил вас решить эту задачу за него. А чтобы решить задачу было проще ниже приведна более подробная формулировка её условия.
Дано дерево (связный неориентированный граф без циклов) из \(n\) вершин. В каждой вершине дерева расположен \(k\)-мерный прямоугольный параллелепипед со сторонами, параллельными осям координат. Параллелепипед задан координатами двух противоположных его углов \((p_1, p_2, \ldots, p_k)\) и \((q_1, q_2, \ldots, q_k)\). Таким образом, внутри параллелепипеда лежат такие и только такие точки \((x_1, x_2, \ldots, x_k)\), что \(p_i \leq x_i \leq q_i\) для всех \(1 \leq i \leq k\). Как известно, между любыми вершинами дерева существует ровно один простой путь (то есть такой путь, что каждая вершина входит в него не более одного раза). Назовём путь хорошим если пересечение параллелепипедов в вершинах этого пути пусто, иными словами, не существует ни одной точки такой, что она лежит во всех параллелепипедах, соответствующих вершинам пути. Назовём длиной пути количество рёбер в нём. Найдите минимальную длину хорошего пути или определите, что ни одного хорошего пути в дереве нет.
В первой строке заданы два целых числа \(n\) и \(k\) (\(2 \leq n \leq 10^6, 2 \leq n \cdot k \leq 10^6\)) — количество вершин в дереве и размерность параллелепипедов, соответственно.
В следующих \(2 \cdot n\) строках содержатся описания параллелепипедов в вершинах.
В строке с номером \(2 \cdot i\) содержатся \(k\) целых чисел \(p_{i, 1}, p_{i, 2}, \ldots, p_{i, k}\) (\(-10^9 \leq p_{i, j} \leq 10^9\)) — координаты одного из углов параллелепипеда в \(i\)-й вершине.
В строке с номером \(2 \cdot i + 1\) содержатся \(k\) целых чисел \(q_{i, 1}, q_{i, 2}, \ldots, q_{i, k}\) (\(p_{i, j} \leq q_{i, j} \leq 10^9\)) — координаты противоположного угла параллелепипеда в \(i\)-й вершине.
В следующих \(n - 1\) строках заданы описания рёбер дерева.
Каждая из этих строк содержит два целых числа \(u_i\) и \(v_i\) (\(1 \leq u_i, v_i \leq n\)), обозначающие наличие ребра между вершинами \(u_i\) и \(v_i\).
Гарантируется, что заданный граф является деревом.
Выведите одно целое число — длину кратчайшего хорошего пути. Если в дереве хороших путей нет выведите « -1 » (без кавычек).
В первом примере единственный хороший путь — это путь между вершинами \(1\) и \(3\). Путь между вершинами \(1\) и \(2\) хорошим не является, так как точка \((1, 2)\) принадлежит прямоугольникам в вершинах \(1\) и \(2\). Путь между вершинами \(2\) и \(3\) хорошим не является, потому что точка \((2, 3)\) принадлежит прямоугольникам в вершинах \(2\) и \(3\).
Во втором примере точка \((1, 1, 1, 1)\) лежит во всех параллелепипедах, поэтому хороших путей не существует.
Тесты к этой задаче состоят из пяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Дополнительные ограничения | ||||
| Группа | Баллы | \(n\), \(k\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | Тесты из условия. |
| 1 | 11 | \(n \leq 100, k \leq 100\) | 0 | |
| 2 | 14 | \(n \leq 500, k \leq 500\) | 0, 1 | |
| 3 | 31 | \(n \cdot k \leq 250\,000\) | 0, 1, 2 | |
| 4 | 21 | \(k = 2\) | – | |
| 5 | 23 | – | 0, 1, 2, 3, 4 | Offline-проверка. |
3 2 0 1 1 2 1 2 2 3 2 3 3 4 1 2 2 3
2
3 4 0 0 0 0 1 1 1 1 1 1 1 1 2 2 2 2 0 0 0 0 2 3 2 3 1 3 2 3
-1