Задача №114076. Эх, дороги
"Таким образом, несмотря на свою значительную железнодорожную сеть, Империя ещё далеко отставала от других культурных государств ..."
Железнодорожная система Империи включает в себя \(N\) городов, соединенных \(N-1\) дорогой так, чтобы из каждого города в каждый можно было добраться по железным дорогам. На случай новой войны Государственный Совет подготовил план, в котором в числе прочего указано, что вся промышленность государства переносится в \(5\) городов для удобства управления. Однако, какие это будут \(5\) городов в проекте не указано.
В силу неразвитости железнодорожной сети прерывание сообщения даже по одной дороге ставит свзяь между промышленными центрами в критическое положение. В связи с этим Государственный Совет попросил вас для разных планов из \(5\) городов сказать, какая суммарная длина дорог, таких, что прерывание сообщения по одной из этих дорог делает какую-то пару из этих \(5\) городов недоступной по оставшимся железным дорогам.
В первой строке вводится число \(N\) (\(5 \leq N \leq 50,000\)) — количество городов в железнодорожной сети.
В каждой из следующих \(N-1\) строк вводится по три числа \(u_i, v_i, w_i\) (\(0 \leq u_i, v_i \leq N-1, 1 \leq w_i \leq 1000\)), что значит, что города \(u_i\) и \(v_i\) соединены дорогой длиной \(w_i\).
Гарантируется, что граф образует дерево.
В следующей строке вводится число \(Q\) (\(1 \leq Q \leq 10,000\)) — количество запросов
В каждой из следующих \(Q\) строк вводится запрос — \(5\) попарно различных городов, для которых нужно ответить, какая суммарная длина дорог, таких, что прерывание сообщения по одной из этих дорог делает какую-то пару из этих \(5\) городов недоступной по оставшимся железным дорогам.
Для каждого запроса выведите одно число — ответ на запрос.
Для прохождения подгруппы нужно пройти все ее тесты.
\(N = 5, Q = 1\) — 7 баллов
\(5 \leq N \leq 50000, 1 \leq Q \leq 10000\), степень каждой вершины не более \(2\) — 23 балла.
\(5 \leq N \leq 50000, 1 \leq Q \leq 100\) — 40 баллов
\(5 \leq N \leq 50000, 1 \leq Q \leq 10000\) — 30 баллов
5 0 1 1 1 2 2 2 3 3 3 4 4 1 4 0 3 1 2
10
6 4 0 4 0 1 2 1 3 9 3 5 1 3 2 5 2 4 0 3 5 2 0 4 1 3 5
21 16