Cho cây ~n~ đỉnh, mỗi đỉnh được tô một trong ~2~ màu trắng hoặc đen. Một cặp đỉnh ~(u, v)~ có thể ghép đôi với nhau khi và chỉ khi thỏa mãn đồng thời:
~u~ và ~v~ được tô màu trắng
Các đỉnh trên đường đi đơn của từ ~u \rightarrow v~ được tô toàn màu đen (trừ ~u~ và ~v~)
Yêu cầu tô màu đỉnh của cây sao cho tạo được nhiều cặp ~(u, v)~ có thể ghép đôi với nhau nhất.
Input
Dòng đầu tiên chứa một số nguyên dương (~T \leq 10~) là số lượng test.
Ở mỗi test:
Dòng đầu tiên của test chứa số nguyên dương ~N~ (~N \leq 5000~) là số lượng nút của cây.
~N - 1~ dòng tiếp theo chứa hai số nguyên ~u, v~ (~1 \leq u, v \leq n~) là cạnh của cây. Dữ liệu đảm bảo đồ thị sẽ là cây
Output
Ghi ra ~T~ dòng, mỗi dòng chứa một số nguyên là kết quả tương ứng với bộ test.
Sample Input 1
2
6
1 2
2 3
2 4
5 6
6 3
3
1 2
2 3
Sample Output 1
5
2
Sample Input 2
2
3
1 2
2 3
5
1 2
2 3
2 4
2 5
Sample Output 2
2
6
Notes
Ở ví dụ 1, test đầu tiên, ta tô màu đỉnh ~2~ để có được ~5~ cặp ~(1, 4)~, ~(1, 3)~, ~(3, 4)~, ~(3, 6)~, ~(5, 6)~.
Ở ví dụ 2, test thứ hai, ta cũng tô màu đỉnh ~2~ để có được ~6~ cặp ~(1, 3)~, ~(1, 4)~, ~(1, 5)~, ~(3, 4)~, ~(3, 5)~, ~(4, 5)~.
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
m=int(input()) n=int(input()) if n==1 and m==2 or n==2 and m==1: print("YES",3) else: if m==3 and n==3 or m==2 and n==3 or m==3 and n==2: print("YES",7) else: if m%2==0 and m==n: print("NO") else: if m%2!=0 or m%2==0 and m%2!=0 or m==n: print("YES",(m-1)*2+3) else: print("NO")
racist
Bài y hệt: ToMau
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Spoil ⚠️