Codeforces Round 947 (Div. 1 + Div. 2) |
---|
Закончено |
У 378QAQ есть дерево с $$$n$$$ вершинами. Изначально все вершины белые.
На дереве есть две шахматные фигуры с названиями $$$P_A$$$ и $$$P_B$$$. $$$P_A$$$ и $$$P_B$$$ изначально расположены на вершинах $$$a$$$ и $$$b$$$ соответственно. За один шаг 378QAQ выполняет следующие действия по порядку:
Изначально вершина $$$a$$$ окрашена в красный цвет. Если $$$a=b$$$, то вместо этого вершина $$$a$$$ окрашена в синий цвет. Обратите внимание, что на каждом шаге обе шахматные фигуры должны быть перемещены. Две фигуры могут находиться в одной вершине в любой момент времени.
378QAQ хочет узнать минимальное количество шагов, которое требуется, чтобы покрасить все вершины в синий цвет.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1\leq t\leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$).
Вторая строка каждого набора входных данных содержит два целых числа $$$a$$$ и $$$b$$$ ($$$1\leq a,b\leq n$$$).
Затем следует $$$n - 1$$$ строка, каждая из которых содержит два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i,y_i \le n$$$), обозначающие ребро между вершинами $$$x_i$$$ и $$$y_i$$$. Гарантируется, что данные ребра образуют дерево.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.
Для каждого набора входных данных выведите минимальное количество шагов, которое требуется, чтобы покрасить все вершины в синий цвет.
321 21 251 21 21 31 41 585 47 11 51 88 37 28 63 4
2 8 13
В первом наборе входных данных 378QAQ может покрасить все вершины в синий цвет следующим образом:
Название |
---|