--->
16 задач
<---
Источники
Гора состоит из площадок, соединенных между собой узкими проходами. На каждой площадке лежит какое-то количество камней. У разных площадок разный рейтинг, зависящий от высоты площадки — чем выше площадка, тем больше ее рейтинг среди камней. Очевидно, что на площадках с более высоким рейтингом лежит большее количество камней.
В один солнечный день главный камень одной из площадок обратил внимание, что вокруг стало очень тесно. Но камни не могут катиться вверх, а на нижние площадки они катиться не хотят из-за плохого рейтинга. Поэтому главный камень пошел на хитрость. Он выбрал M камней и сказал каждому из них, что где-то внизу появилась замечательная площадка с самым высоким рейтингом на горе. Для полной правдоподобности он составил карту площадок, на которые можно скатиться с его площадки. Всего (включая переполненную площадку) оказалось N площадок. Поскольку главный камень ленивый, он не стал рисовать все пути между площадками, а просто нарисовал минимальное количество проходов между площадками, чтобы из его площадки можно было добраться в любую, находящуюся ниже. Он показал каждому из M камней эту карту и объяснил, где находится замечательная площадка (чтобы камень запомнил путь). Причем, чтобы главные камни нижних площадок не имели к нему претензий из-за такого нашествия, некоторым камням он показал на другие площадки, чем остальным. Чтобы не создать лавину, он сказал камням катиться с небольшим интервалом между собой. Немного подумав, он решил, что можно пускать камни парами, чтобы пространство быстрее освободилось. Камни ему поверили и стали собираться в дорогу.
Камни не любят скучать, поэтому каждая пара решила посчитать, сколько времени они будут катиться вместе, и, может быть, перестроить пары, чтобы увеличить это время. На то, чтобы скатиться по проходу с одной площадки в следующую, не заходя по пути на другие площадки, камень тратит одну минуту. Но складывать числа камни не умеют, в этом им требуется ваша помощь.
В первой строке входного файла записаны два целых числа - N и K , где 1 ≤ N ≤25000, K = M / 2, 0 ≤ M ≤ 2000 . В следующих ( N –1) строках находятся пары чисел i и j , означающие, что из i -й площадки можно напрямую скатиться на j -ю. Площадки занумерованы числами от 1 до N , верхняя площадка, откуда катятся камни, может иметь любой номер. Записанных пар номеров площадок достаточно, чтобы определить путь из самой верхней площадки до любой другой. Дальше идут K строк, на каждой строке через пробел записана пара чисел a и b (1 ≤ a , b ≤ N ) , обозначающая пункты назначения для очередной пары камней: первый камень катится на площадку a , а второй — на площадку b .
В выходной файл нужно вывести K строк, на каждой строке должно находиться по три целых числа a , b и c , записанных через пробел. Эти числа означают, что пара камней, направляющихся на площадки a и b , будет катиться вместе c минут. Тройки чисел нужно выдавать в том же порядке, в котором перечислены соответствующие им пары во входном файле.
6 2 1 2 1 3 1 4 3 5 3 6 2 4 5 6
2 4 0 5 6 1
Гора состоит из площадок, соединенных между собой узкими проходами. На каждой площадке лежит какое-то количество камней. У разных площадок разный рейтинг, зависящий от высоты площадки — чем выше площадка, тем больше ее рейтинг среди камней. Очевидно, что на площадках с более высоким рейтингом лежит большее количество камней.
В один солнечный день главный камень одной из площадок обратил внимание, что вокруг стало очень тесно. Но камни не могут катиться вверх, а на нижние площадки они катиться не хотят из-за плохого рейтинга. Поэтому главный камень пошел на хитрость. Он выбрал M камней и сказал каждому из них, что где-то внизу появилась замечательная площадка с самым высоким рейтингом на горе. Для полной правдоподобности он составил карту площадок, на которые можно скатиться с его площадки. Всего (включая переполненную площадку) оказалось N площадок. Поскольку главный камень ленивый, он не стал рисовать все пути между площадками, а просто нарисовал минимальное количество проходов между площадками, чтобы из его площадки можно было добраться в любую, находящуюся ниже. Он показал каждому из M камней эту карту и объяснил, где находится замечательная площадка (чтобы камень запомнил путь). Причем, чтобы главные камни нижних площадок не имели к нему претензий из-за такого нашествия, некоторым камням он показал на другие площадки, чем остальным. Чтобы не создать лавину, он сказал камням катиться с небольшим интервалом между собой. Немного подумав, он решил, что можно пускать камни парами, чтобы пространство быстрее освободилось. Камни ему поверили и стали собираться в дорогу.
Камни не любят скучать, поэтому каждая пара решила посчитать, сколько времени они будут катиться вместе, и, может быть, перестроить пары, чтобы увеличить это время. На то, чтобы скатиться по проходу с одной площадки в следующую, не заходя по пути на другие площадки, камень тратит одну минуту. Но складывать числа камни не умеют, в этом им требуется ваша помощь.
В первой строке входного файла записаны два целых числа — N и K , где 1 ≤ N ≤ 500000 , K = M / 2 , 0 ≤ M ≤ 1000000 . В следующих ( N –1) строках находятся пары чисел i и j , означающие, что из i -й площадки можно напрямую скатиться на j -ю. Площадки занумерованы числами от 1 до N , верхняя площадка, откуда катятся камни, может иметь любой номер. Записанных пар номеров площадок достаточно, чтобы определить путь из самой верхней площадки до любой другой. Дальше идут K строк, на каждой строке через пробел записана пара чисел a и b (1 ≤ a , b ≤ N ) , обозначающая пункты назначения для очередной пары камней: первый камень катится на площадку a , а второй — на площадку b .
В выходной файл нужно вывести K строк, на каждой строке должно находиться по три целых числа a , b и c , записанных через пробел. Эти числа означают, что пара камней, направляющихся на площадки a и b , будет катиться вместе c минут. Тройки чисел нужно выдавать в том же порядке, в котором перечислены соответствующие им пары во входном файле.
1 ≤ N ≤ 25 000, 1 ≤ M ≤ 2 000. Решение оценивается в 55 баллов.
Дополнительные ограничения отсутствуют. Решение оценивается в 45 баллов.
6 2 1 2 1 3 1 4 3 5 3 6 2 4 5 6
2 4 0 5 6 1
Дано дерево из n вершин. У каждой вершины есть цвет. Нужно обработать q запросов ( v i , c i ): найти расстояние от v i до ближайшей к v i вершины цвета c i . Расстоянием между вершинами называется минимальное количество рёбер в пути между ними.
На первой строке число n ( 1 ≤ n ≤ 10 5 ), следующая строка содержит числа p 1 , p 2 , ..., p n - 1 . 0 ≤ p i < i . p i – отец вершины i в дереве. Далее строка с числами a 0 , a 1 , ..., a n - 1 . 0 ≤ a i < n . a i – цвет вершины i . Далее строка с числом q ( 1 ≤ q ≤ 10 5 ). Следующие q строк содержат запросы v iq i ( 0 ≤ v i < n , 0 ≤ c i < n ).
Для каждого запроса выведите одно число – расстояние до ближайшей вершины нужного цвета, или - 1 , если в дереве нет вершин такого цвета.
5 0 1 1 3 1 2 3 2 1 9 0 1 0 2 0 3 1 0 2 1 2 2 3 3 3 1 4 2
0 1 2 -1 2 1 2 1 1
На родной планете Чубакки растет очень большое дерево, на ветках которого вуки строят свои домики. Чубакке стало интересно, как быстро можно попасть из некоторых домиков в другие. Вам придется ответить на несколько его вопросов, чтобы он вас отпустил.
Вам дано дерево с N вершинами порядка K , то есть каждая вершина дерева может иметь не более K потомков. Дерево создано по принципу "минимальной энергии": вершины в нем располагается на новом уровне только тогда, когда все места на предыдущем уровне (слева направо) заняты. В таком же порядке вершины дерева пронумерованы, начиная с 1.
Вам необходимо ответить на Q запросов вида " x y ", где ответом является расстояние (количество ребер в минимальном пути) в данном дереве между вершинами с номерами x и y .
Первая строка содержит три целых числа: N ( 1 ≤ N ≤ 10 15 ), K ( 1 ≤ K ≤ 1000 ) и Q ( 1 ≤ Q ≤ 100000 ). Каждая из следующих Q строк содержит пару чисел x y ( 1 ≤ x , y ≤ N , x ≠ y ) - запросы, описанные в условии.
Выведите Q строк, в каждой из которых одно целое число - ответ на соответствующий запрос.
Решения, работающие при 1 ≤ N , Q ≤ 1000 , будут оцениваться в 20 баллов. Решения, работающие при 1 ≤ N , Q ≤ 100000 , будут оцениваться в 50 баллов.
7 2 3 1 2 2 1 4 7
1 1 4
9 3 3 8 9 5 7 8 4
2 2 3
В Флатландии идет пора реформ. Недавно была проведена реформа дорог, так что теперь по дорогам страны из любого города можно добраться в любой другой, причем только одним способом. Также была проведена реформа волшебников, так что в каждом городе остался ровно один волшебник. Теперь же началась реформа почтовой системы.
Недавно образованное почтовое агентство «Экс-Федя» предлагает уникальную услугу — коллективную посылку. Эта услуга позволяет отправлять посылки жителям всех городов на каком-либо пути по цене обычной посылки. Удивительно, но пользоваться такой услугой стали только волшебники Флатландии, которые стали в большом количестве отправлять друг другу магические кактусы. Агентство столкнулось с непредвиденной проблемой: как известно, все волшебники живут в башнях и мало того, что не строят в них лестницы, так еще время от времени меняют их высоту. Поэтому, чтобы доставить посылку волшебнику, который живет в башне высотой h , курьеру агентства требуется иметь с собой не менее h метров веревки.
Вам поручено руководить отделом логистики — по имеющимся данным о высотах башен и об их изменениях вам нужно определять минимальную длину веревки, которую нужно выдать курьеру, который доставляет посылки между городами i и j .
Первая строка входного файла содержит число n — количество городов в Флатландии ( 1 ≤ n ≤ 50 000 ). Во второй строке находится n положительных чисел, не превосходящих 10 5 — высоты башен в городах. В следующих n - 1 строках содержится по два числа u i и v i — описание i -й дороги, 1 ≤ u i , v i ≤ n , u i ≠ v i . В следующий строке содержится число k — количество запросов ( 1 ≤ k ≤ 100 000 ). В следующих k строках содержатся описания запросов в следующем формате:
Для каждого запроса доставки посылок выведите минимальную длину веревки, которую необходимо выдать курьеру.
20 баллов — ( 1 ≤ n, k ≤ 100) .
30 баллов — каждый город соединен дорогами не более чем с двумя другими.
50 баллов — полные ограничения.
3 1 2 3 1 3 2 3 5 ? 1 2 ! 1 5 ? 2 3 ! 3 2 ? 1 2
3 3 5
1 100 5 ! 1 1 ? 1 1 ! 1 1000 ? 1 1 ! 1 1
1 1000