Задача №115394. Древо жизни
В сердце древнего королевства растет легендарное Древо Жизни — единственное в своем роде и источник магической силы всего мира. Дерево состоит из \(n\) узлов. Каждый узел этого дерева — это волшебный источник, связанный с другими такими же источниками через магические каналы (ребра). Всего в дереве \(n-1\) каналов, \(i\)-й из которых соединяет узлы \(v_i\) и \(u_i\). Также между любыми двумя узлами в дереве существует единственный простой путь по каналам.
Однако магическая энергия, текущая через эти каналы, должна быть сбалансирована, иначе мощь Древа Жизни может нарушить естественный порядок и вызвать катастрофические последствия. Мудрецы королевства обнаружили, что когда два магических канала сходятся в одном узле, между ними возникает опасная «магическая резонансная вибрация». Чтобы защитить Древо Жизни и сохранить его баланс, необходимо выбрать несколько путей и провести через них специальные ритуалы. Путь — это последовательность различных узлов \(v_1, v_2, \ldots, v_k\) для натурального \(k\), где каждая пара соседних узлов \(v_i\) и \(v_{i+1}\) соединена каналом (для любого \(1 \leq i \leq k - 1\)). При проведении мудрецами ритуала через такой путь блокируются все резонансные вибрации между парами соседних каналов в пути, а именно между каналами \((v_i, v_{i+1})\) и \((v_{i+1}, v_{i+2})\) для каждого \(1 \leq i \leq k - 2\).
Задача мудрецов: выбрать минимальное количество путей и провести через них ритуалы, чтобы заблокировать все резонансные вибрации. Это означает, что для каждой пары каналов, исходящих из одного узла, должен существовать хотя бы один выбранный путь, который охватывает оба этих канала.
Помогите мудрецам найти минимальное количество таких путей, чтобы магический баланс Древа Жизни был сохранен, и его сила продолжала питать весь мир!
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число \(t\) \((1 \leq t \leq 40\,000)\) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число \(n\) \((2 \leq n \leq 500\,000)\) — количество узлов в Древе Жизни.
В \(i\)-й из следующих \(n - 1\) строк каждого набора входных данных содержатся два целых числа \(v_i\) и \(u_i\) (\(1 \leq v_i < u_i \leq n\)) — канал, соединяющий узлы \(v_i\) и \(u_i\).
Гарантируется, что между любыми двумя узлами существует единственный простой путь по каналам.
Гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(500\,000\).
Для каждого набора входных данных выведите одно целое число — минимальное количество путей, которое нужно выбрать мудрецам, чтобы предотвратить катастрофу.
В первом тестовом примере достаточно выбрать путь \((1, 2, 3, 4)\), таким образом ответ \(1\).
Во втором тестовом примере нет пар каналов, исходящих из одного узла, поэтому ответ \(0\).
4 4 1 2 2 3 3 4 2 1 2 8 3 7 2 4 1 2 2 5 3 6 1 3 3 8 6 2 3 1 2 3 6 1 5 1 4
1 0 7 3