Codeforces Round 798 (Div. 2) |
---|
Закончено |
Байтландия — прекрасная земля, известная своими красивыми деревьями.
Миша нашел бинарное дерево с $$$n$$$ вершинами, пронумерованными от $$$1$$$ до $$$n$$$. Бинарное дерево — это ациклический связный неориентированный граф, содержащий $$$n$$$ вершин и $$$n - 1$$$ ребер. Каждая вершина имеет степень не больше $$$3$$$, а корнем является вершина с номером $$$1$$$ и имеет степень не больше $$$2$$$.
К сожалению, корень дерева был заражен. Следующий процесс происходит $$$n$$$ раз:
Так как Мише некогда думать, скажите ему, какое максимальное количество вершин он может спасти от заражения (обратите внимание, что удаленные вершины не считаются спасенными).
Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1\leq t\leq 5000$$$) — количество наборов входных данных. Далее следуют наборы входных данных.
В первой строке каждого набора задано одно целое число $$$n$$$ ($$$2\leq n\leq 3\cdot 10^5$$$) — количество вершин дерева.
В $$$i$$$-й из следующих $$$n-1$$$ строк набора входных данных задано два числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$), обозначающих очередное ребро дерева.
Гарантируется, что граф является бинарным деревом с корнем в вершине $$$1$$$. Также гарантируется, что сумма $$$n$$$ по всем наборам не превышает $$$3\cdot 10^5$$$.
Для каждого набора входных данных выведите единственное целое число — ответ на задачу.
4 2 1 2 4 1 2 2 3 2 4 7 1 2 1 5 2 3 2 4 5 6 5 7 15 1 2 2 3 3 4 4 5 4 6 3 7 2 8 1 9 9 10 9 11 10 12 10 13 11 14 11 15
0 2 2 10
В первом наборе входных данных единственным возможным действием является удаление вершины $$$2$$$, после чего мы спасли $$$0$$$ вершин.
Во втором наборе входных данных, если мы удалим вершину $$$2$$$, мы сможем спасти вершины $$$3$$$ и $$$4$$$.
Название |
---|