Я все перепробовал ни один не подходит даже ИИ в шоке кто это вообще придумал

Тренажер ... Алгоритмы Все дороги ведут в Рим! Все дороги ведут в Рим! +300 Не решалось Сложно Графы SQRT-декомпозиция Следующая задача Условия задачи Решения Баллы и штрафы Ограничения Требования к прохождению Все дороги ведут в Рим! Завтра в столице будут проводится крупные торги, куда приедут торговцы со всех городов Империи. В Римской Империи есть n городов, связанных между собой дорогами. Разумеется, из любого города можно добраться в Рим, и сделать это можно единственным образом, если не посещать никакой город дважды. На рассвете из некоторых городов в сторону столицы выедут караваны с товаром, каждый из них имеет свой коэффициент прибыли. Об этом узнали грабители и решили устроить идеальное ограбление. Для этого они хотят расположиться в одном из городов, чтобы грабить все проезжающие через него караваны. Но в Римской империи есть своя система безопасности: чем ближе город к столице, тем более влиятельны там силы правопорядка. Если через город, находящийся на расстоянии d от Рима, проезжает караван с коэффициентом доходности c, то грабители, находясь в этом городе, смогут получить (d + 1) ⋅ c прибыли с этого каравана. Так как грабители не знают, сколько караванов и из каких городов выдвинутся на торги, им интересно узнать, какую максимальную прибыль они могут получить для q гипотетических запросов. Система оценки Обозначим за Ksum сумму k по всем наборам. Подзадача 1(10 баллов): n ≤ 3000, Ksum ≤ 3000, t = 1 Подзадача 2(35 баллов): n ≤ 105, Ksum ≤ 105, t = 1, необходимые подзадачи — 1 Подзадача 3(25 баллов): n ≤ 105, Ksum ≤ 105, t = 2, необходимые подзадачи — 1, 2 Подзадача 4(30 баллов): n, Ksum без дополнительных ограничений, t = 2, необходимые подзадачи — 1, 2, 3 Обратите внимание, что для прохождения любой группы тестов ваша программа не обязана выдавать верный ответ на примерах из условия. Формат входных данных Первая строка содержит одно целое число n (2 ≤ n ≤ 4 ⋅ 105) — количество городов в империи. Города пронумерованы целыми числами от 1 до n. Рим — город номер 1. В следующей n - 1 строке содержится описание дорог в виде двух чисел u и v (1 ≤ u, v, ≤ n). Это означает, что между городами u и v есть дорога. Далее содержатся два целых числа q и t. q (1 ≤ q ≤ 4 ⋅ 105) — количество запросов. t (1 ≤ t ≤ 2) — тип описания запросов. Затем следует описание запросов. В начале каждого описания запроса содержится строка с одним целом числом k (1 ≤ k < n) — количеством караванов. Далее дается описание всех караванов, состоящее из k строк. В зависимости от t описание каравана имеет следующий вид: Если t = 1 то в i-й строке содержится 2 целых числа — vi (2 ≤ vi ≤ n) и ci (1 ≤ ci ≤ 106). i-й караван выдвигается из города vi и имеет коэффициент доходности ci. Гарантируется что внутри одного запроса все vi различны. Если t = 2 то в i-й строке содержится 2 целых числа — ui (0 ≤ ui < n - 1) и ci (1 ≤ ci ≤ 106). Пусть lastans — ответ на предыдущий запрос. Для первого запроса last_{ans} = 0. Тогда i-й караван текущего запроса выдвигается из города (ui + lastans) mod (n - 1) + 2, где mod обозначает операцию взятия остатка от деления. ci соответственно коэффициент доходности i-го каравана. Гарантируется что внутри одного запроса все ui различны. Гарантируется что сумма k по всем наборам не превосходит 4 ⋅ 105. Формат выходных данных Выведите q целых чисел. i-е число — максимальное значение прибыли для i-го запроса. Пример 1 Входные данные 4 1 2 2 3 3 4 1 1 2 2 10 3 3 Выходные данные 26 Пример 2 Входные данные 5 1 2 3 1 4 3 3 5 2 2 3 0 7 3 4 2 4 3 1 4 2 2 3 1 Выходные данные 16 14