Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии $$$t \le 10^4$$$, $$$n \le 2 \cdot 10^5$$$ и сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$. Вы можете делать взломы только в том случае, если решили все версии этой задачи.
Соперники Аксиал и Нифе в очередной раз поссорились и решили разрешить спор, сыграв в игру на дереве.
Им дано дерево с $$$n$$$ вершинами, пронумерованными от $$$1$$$ до $$$n$$$. В каждой вершине записано либо $$$0$$$, либо $$$1$$$. Изначально в двух различных вершинах $$$x$$$ и $$$y$$$ записано $$$0$$$, а во всех остальных вершинах записано $$$1$$$.
Игроки ходят по очереди, первым ходит Аксиал. На каждом ходу текущий игрок выбирает вершину $$$v$$$, в которой записано $$$1$$$, и меняет её значение на $$$0$$$. Перед изменением значения в вершине $$$v$$$ обозначим через $$$c_v$$$ количество соседей вершины $$$v$$$, в которых записано $$$0$$$. Если $$$c_v = 1$$$, текущий игрок получает одно очко. Иначе он не получает очков. Игра заканчивается, когда во всех вершинах записано $$$0$$$.
Пусть $$$p$$$ и $$$q$$$ — итоговое количество очков Аксиала и Нифе соответственно. Аксиал хочет максимизировать $$$p - q$$$, а Нифе — минимизировать эту разность. Определите значение $$$p - q$$$ в конце игры, если оба игрока играют оптимально.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
В первой строке каждого набора входных данных находятся три целых числа $$$n$$$, $$$x$$$ и $$$y$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le x, y \le n$$$, $$$x \ne y$$$) — количество вершин в дереве и две вершины, в которых изначально записано $$$0$$$.
В каждой из следующих $$$n - 1$$$ строк находятся два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$), обозначающих ребро между вершинами $$$u$$$ и $$$v$$$.
Гарантируется, что данный граф является деревом.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — значение $$$p - q$$$ в конце игры.
43 1 21 22 34 1 41 22 33 43 1 31 22 36 2 31 21 31 41 51 6
1100
На рисунках ниже в синих вершинах изначально записано $$$0$$$, а в белых — $$$1$$$.
В первом примере начальное состояние выглядит так:
Аксиал меняет значение в вершине $$$3$$$ на $$$0$$$. У неё ровно один сосед, в котором записано $$$0$$$, поэтому Аксиал получает одно очко. Следовательно, $$$p - q=1$$$.
Во втором примере начальное состояние выглядит так:
Аксиал может изменить значение в вершине $$$2$$$ или вершине $$$3$$$ на $$$0$$$ и получить одно очко. После этого у оставшейся вершины будет два соседа, в которых записано $$$0$$$, поэтому Нифе не получит очков. Следовательно, $$$p - q=1$$$.
В третьем примере начальное состояние выглядит так:
Единственный возможный ход — изменить значение в вершине $$$2$$$ на $$$0$$$. У неё два соседа, в которых записано $$$0$$$, поэтому Аксиал не получает очков. Следовательно, $$$p - q=0$$$.
