Дано реберновзвешенное дерево.
A — некоторое подмножество вершин дерева. Изначально A пусто, потом поступают запросы добавить вершину в A или удалить вершину из A.
После каждого запроса требуется выдавать вес минимального поддерева, содержащего все вершины из A. Вес поддерева определим как сумму весов рёбер, входящих в это поддерево.
Исходные данные
В первой строке записано целое число n — размер дерева (1 ≤ n ≤ 3 · 105).
Затем в n−1 строках описаны рёбра дерева. Описание каждого ребра имеет вид “u v w” — концы ребра и его вес (1 ≤ u, v ≤ n, u ≠ v, 0 ≤ w ≤ 109). Гарантируется, что эти рёбра образуют дерево.
В следующей строке записано целое число q — количество запросов (1 ≤ q ≤ 3 · 105).
Затем в q строках описаны запросы. Каждый запрос имеет вид “t v”, где t — либо “+
” (добавить вершину в A), либо “-
” (удалить вершину из A), v — номер вершины (1 ≤ v ≤ n). Гарантируется, что никогда не просят добавить вершину, которая уже находится в A, а также никогда не просят удалить вершину, которой в A нет.
Результат
Выведите q чисел — вес минимального поддерева, содержащего все вершины из A, после очередного изменения. Если A пусто, выдавайте 0.
Пример
исходные данные | результат |
---|
5
1 2 1
2 3 10
3 4 100
3 5 1000
8
+ 2
+ 5
+ 4
- 5
+ 1
- 4
- 2
- 1
| 0
1010
1110
110
111
1
0
0
|
Автор задачи: Алексей Данилюк
Источник задачи: Петрозаводск лето 2018. t.me/umnik_team Contest