Задача №114358. Фишки на дереве
У вас есть дерево на \(n\) вершин. Каждая вершина может содержать фишку. Изначально, все вершины пусты.
Вы должны обработать два типа запросов:
-
Положить фишку в вершину.
- Удалить фишку из вершины.
После каждого запроса, вам необходимо вывести удалённость текущей конфигурации фишек.
Удалённость определена как минимальное число операций необходимых для того, чтобы переместить все фишки в одну какую-то вершину. В одной операции вы можете переместить фишку из её вершины в любую соседнюю вершину. Любая вершина может содержать сколько угодно фишек.
Заметим, что эти операции необходимы только для определения удалённости, и, на самом деле, они не выполняются.
Первая строка содержит единственное целое число \(n (1 \leq n \leq 10^5)\), количество вершин дерева.
Следующие \(n-1\) строк описывают рёбра дерева. \(i\) строка содержит два целых числа \(u\) и \(v (1 \leq u, v \leq n)\), индексы вершин, соединённых \(i\) ребром.
Гарантируется, что эти ребра образуют дерево.
Следующая строка содержит единственное число \(q (1 \leq q \leq 10^5)\), количество запросов.
Следующие \(q\) строк описывают запросы. Каждый запрос описан как " c v "\( (1 \leq v \leq n)\). Символ \(c\) равен " + " для первого типа запросов и " - " для второго типа. \(v\) — это индекс вершины, к которой применяется запрос. Гарантируется, что если это запрос первого типа, то в вершине \(v\) нет фишки, и если это запрос второго типа, то в вершине \(v\) была фишка. Также гарантируется, что после каждого запроса есть хотя бы одна фишка в дереве.
Для каждого запроса выведите строку с единственным целым числом: удаленность дерева после применения этого запроса.
\(1 \leq n \leq 100, 1 \leq q \leq 100\) - 30 баллов (тесты 1-27)
\(1 \leq n \leq 1000, 1 \leq q \leq 1000\) - 30 баллов (тесты 28-52)
\(1 \leq n \leq 100000, 1 \leq q \leq 100000\) - 40 баллов (тесты 53-133)
3 1 2 2 3 4 + 1 + 3 + 2 - 1
0 2 2 1
6 1 2 2 3 3 4 4 5 2 6 5 + 1 + 4 + 5 - 5 + 6
0 3 4 3 4