Mabư Béo Trèo Cây

View as PDF

Submit solution


Points: 0.01
Time limit: 2.0s
Memory limit: 512M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Mabư Béo có bài tập trèo cây ngày hôm nay. Nhưng sau những giờ đạp xe từ đầu tuần mà khiến hắn mệt mỏi đến tận bây giờ, hắn ta quyết định trì hoãn. Để rồi cây duy nhất hắn chinh phục được hôm nay là cây kem béo bở hắn đang cầm trên tay lúc này.

Piccolo thấy vậy buồn lắm, bèn tận dụng quãng thời gian cậu trì hoãn để thách đố một bài toán tô màu cây như sau:

Một cây hoàn mỹ được định nghĩa như sau:

  • Tồn tại ít nhất ~1~ cách để tô mỗi nút của cây bằng hai màu: đen hoặc trắng, sao cho mỗi nút có đúng một và chỉ một nút kề nó được tô cùng màu.

Piccolo đưa cho Mabư Béo một cái cây, có gốc là ~1~, và số đỉnh chẵn. Nhiệm vụ của Mabư Béo là biến cây này trở thành cây hoàn mỹ bằng một số thao tác đảo các nút trong cây. Một thao tác được mô tả như sau:

  • Chọn một nút ~u~ (~u > 1~), Sau đó chọn một nút ~v~ thỏa mãn không phải một trong những hậu duệ của nút ~u~ (Theo định nghĩa, ~u~ cũng là một trong những hậu duệ của ~u~).

  • Bỏ cạnh nối nút ~u~ với nút cha của ~u~, sau đó thêm cạnh mới nối ~u~ với ~v~.

Hỏi, số thao tác ít nhất để Mabư Béo cần thực hiện để khiến cây đã cho trở thành Cây Hoàn Mỹ?

Input

Mỗi file test chứa nhiều trường hợp test. Dòng đầu của mỗi file chứa số trường hợp test trong file ~T~ (~1 \le T \le 100~). Mỗi trường hợp test được mô tả như sau:

Dòng đầu chứa số nguyên ~N~ (~2 \le N \le 10^5~) - số nút trong cây mà Piccolo đã đưa. ~N~ luôn chẵn.

~N - 1~ dòng sau, dòng thứ ~i~ chứa hai số nguyên ~x_i~, ~y_i~ (~1 \le x_i, y_i \le N~), thể hiện rằng có cạnh nối giữa hai nút ~x_i~ và ~y_i~. Dữ liệu đảm bảo các cạnh đã cho tạo thành một cây hoàn chỉnh.

Tổng của các ~N~ trong tất cả các trường hợp test không vượt ~10^5~.

Output

Với mỗi trường hợp test, in ra một số nguyên duy nhất, thể hiện số thao tác ít nhất cần thực hiện để khiến cây trở nên hoàn mỹ.

Sample Input 1

4
12
7 6
12 10
9 5
8 12
1 12
11 5
1 9
3 7
1 7
2 5
12 4
8
1 3
1 4
3 5
3 6
4 2
4 7
4 8
4
1 2
2 3
3 4
4
1 2
1 3
1 4

Sample Output 1

2
2
0
1

Notes

Ở trường hợp ví dụ đầu tiên, đây là cây ban đầu:

image

Mabư Béo có thể chọn ngắt kết nối nút ~3~ và ~4~ với cha của chúng, sau đó nối chúng với nút ~8~ với ~2~ lần lượt. Sau đó, tô các nút ~1~, ~2~, ~3~, ~4~, ~8~, ~9~ bằng màu trắng. Các nút còn lại sẽ được tô màu đen.

image


Comments

Please read the guidelines before commenting.


There are no comments at the moment.