ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Петрозаводск лето 2018. t.me/umnik_team Contest

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

B. Древесная оболочка

Ограничение времени: 5.0 секунды
Ограничение памяти: 256 МБ
Дано реберновзвешенное дерево.
A — некоторое подмножество вершин дерева. Изначально A пусто, потом поступают запросы добавить вершину в A или удалить вершину из A.
После каждого запроса требуется выдавать вес минимального поддерева, содержащего все вершины из A. Вес поддерева определим как сумму весов рёбер, входящих в это поддерево.

Исходные данные

В первой строке записано целое число n — размер дерева (1 ≤ n ≤ 3 · 105).
Затем в n−1 строках описаны рёбра дерева. Описание каждого ребра имеет вид “u v w” — концы ребра и его вес (1 ≤ u, vn, uv, 0 ≤ w ≤ 109). Гарантируется, что эти рёбра образуют дерево.
В следующей строке записано целое число q — количество запросов (1 ≤ q ≤ 3 · 105).
Затем в q строках описаны запросы. Каждый запрос имеет вид “t v”, где t — либо “+” (добавить вершину в A), либо “-” (удалить вершину из A), v — номер вершины (1 ≤ vn). Гарантируется, что никогда не просят добавить вершину, которая уже находится в 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
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2119. Древесная оболочка