Онер — это джанглер — в этой роли вы охотитесь на монстров в джунглях. Учитывая количество деревьев, которые он видит в джунглях, неудивительно, что он обожает задачи с запросами на деревьях.
Вам дано дерево из $$$n$$$ вершин, корень которого находится в вершине $$$1$$$. Каждая вершина либо содержит монстра, либо не содержит.
Вам нужно найти минимальное целое число $$$k$$$, такое что существуют $$$k$$$ путей, удовлетворяющих следующим условиям:
- Каждый путь должен начинаться в корне (вершина $$$1$$$).
- Каждая вершина с монстром должна быть включена хотя бы в один из этих путей. Вершина считается включенной в путь, если она является одной из вершин пути, включая его концы.
Чтобы сделать эту задачу более сложной, вам также нужно ответить на $$$q$$$ запросов. Для каждого запроса вам дается вершина $$$v$$$. Для каждой вершины $$$w$$$ в поддереве $$$v$$$ ее статус инвертируется — та, что содержит монстра, начинает не содержать его, а та, что не содержит монстра, начинает содержать его. После каждого запроса вам нужно снова решить исходную задачу с обновленными статусами.
Обратите внимание, что запросы являются кумулятивными, поэтому эффекты каждого запроса переносятся на будущие запросы.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 20\,000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 250\,000$$$) — количество вершин в дереве.
Следующая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$a_i \in \{0, 1\}$$$), обозначающих начальные статусы. Если $$$a_i = 1$$$, вершина $$$i$$$ содержит монстра; если $$$a_i = 0$$$, то не содержит.
Каждая из следующих $$$n-1$$$ строк содержит по два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n, u \ne v$$$), описывающих ребро между вершинами $$$u$$$ и $$$v$$$. Гарантируется, что эти ребра образуют дерево.
Следующая строка содержит одно целое число $$$q$$$ ($$$0 \le q \le 250\,000$$$) — количество запросов.
Каждая из следующих $$$q$$$ строк содержит одно целое число $$$v_i$$$ ($$$1 \le v_i \le n$$$) — вершина, заданная для $$$i$$$-го запроса.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$250\,000$$$.
Гарантируется, что сумма значений $$$q$$$ по всем наборам входных данных не превосходит $$$250\,000$$$.
Выведите $$$q + 1$$$ строку. Первая строка должна содержать минимальное количество путей $$$k$$$ для начального состояния. Каждая последующая строка должна содержать ответ после каждого запроса.
270 1 0 1 1 0 01 61 77 33 27 55 44246720 11 2221
21123101
Набор входных данных 1:
Начальное состояние: Монстры находятся в вершинах $$$\{2, 4, 5\}$$$. Нам нужно два пути: $$$1 \to 7 \to 3 \to 2$$$ и $$$1 \to 7 \to 5 \to 4$$$. Ответ — $$$2$$$.
После запроса 1 ($$$v=2$$$): Монстры находятся в вершинах $$$\{4, 5\}$$$. Нам нужен только один путь, $$$1 \to 7 \to 5 \to 4$$$. Ответ — $$$1$$$.
После запроса 2 ($$$v=4$$$): Монстр находится в вершине $$$\{5\}$$$. Нам нужен только один путь, $$$1 \to 7 \to 5$$$. Ответ — $$$1$$$.
После запроса 3 ($$$v=6$$$): Монстры находятся в вершинах $$$\{5, 6\}$$$. Нам нужно два пути, $$$1 \to 7 \to 5$$$ и $$$1 \to 6$$$. Ответ — $$$2$$$.
После запроса 4 ($$$v=7$$$): Монстры находятся в вершинах $$$\{2, 3, 4, 6, 7\}$$$. Нам нужно три пути, $$$1 \to 6$$$, $$$1 \to 7 \to 5 \to 4$$$ и $$$1 \to 7 \to 3 \to 2$$$. Ответ — $$$3$$$.
На следующем рисунке изображено дерево из примера:
Набор входных данных 2:
Начальное состояние: Монстр находится в вершине $$$\{2\}$$$. Нам нужен один путь: $$$1 \to 2$$$. Ответ — $$$1$$$.
После запроса 1 ($$$v=2$$$): Монстров нет. Нам нужно ноль путей. Ответ: $$$0$$$.
После запроса 2 ($$$v=1$$$): Монстры находятся в вершинах $$$\{1,2\}$$$. Нам нужен один путь: $$$1 \to 2$$$. Ответ: $$$1$$$.
