Tô Màu

Xem dạng PDF
Gửi bài giải
Điểm: 0,01
Giới hạn thời gian: 0.75s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Tác giả:
bedao
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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

Hãy đọc nội quy trước khi bình luận.


  • -7
    danglebinhnguyen2014  đã bình luận lúc 2, Tháng 4, 2025, 12:23

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 0
    LeTranTienDat  đã bình luận lúc 2, Tháng 4, 2025, 12:21

    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")


  • -2
    ducsieumanh1hitlanamguku  đã bình luận lúc 1, Tháng 4, 2025, 8:20

    racist


  • 5
    tuananhtank2708  đã bình luận lúc 29, Tháng 3, 2025, 12:15

    Bài y hệt: ToMau


  • -6
    daohuutri50  đã bình luận lúc 28, Tháng 3, 2025, 3:10

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -3
    LA_NTTANH  đã bình luận lúc 26, Tháng 3, 2025, 1:05

    Bài này dùng quy hoạch động hình học tam biến nhe


  • 15
    YougiTuber  đã bình luận lúc 25, Tháng 3, 2025, 16:02 ← chỉnh sửa

    Spoil ⚠️

    Dùng dp tree

    Short solution:

    ~dp[u][cnt]~ là số cặp màu trắng đến được nhau mà không đi qua đỉnh trắng nào khác ở trên đường đi này, và có ~cnt~ đỉnh trắng có thể đi lên phía trên mà không gặp đỉnh trắng nào khác.

    Long solution:

    Xét trường hợp đỉnh u tô màu trắng, với v là con của u, nếu có cnt đỉnh màu trắng có thể đi trực tiếp từ cây con gốc v lên, mà không đi qua đỉnh trắng nào khác, thì số cặp tăng lên là cnt

    Ví dụ

    Trong hình này, cnt bằng ~3~

    Công thức quy hoạch động: ~dp[u][cnt]~ là số cặp màu trắng đến được nhau mà không đi qua đỉnh trắng nào khác ở trên đường đi này, và có ~cnt~ đỉnh trắng có thể đi lên phía trên mà không gặp đỉnh trắng nào khác.

    Khởi tạo ~dp[u][cnt] = -oo~ và ~dp[u][0] = 0~

    Xét đỉnh u màu trắng

    Trạng thái tạo ra được cnt = 1 do đỉnh u màu trắng, thì chỉ có u đi lên trên mà không gặp màu trắng nào, số cặp màu trắng tăng lên là số đỉnh trắng từ cây con gốc v đi lên được u, chính là cnt.

    Vì vậy, với mỗi đỉnh v, ta sẽ chọn trạng thái cnt tốt nhất để ~dp[v][cnt] + cnt~ tối đa.

    ~dp[u][1] = \sum_{}^{} max(dp[v][cnt] + cnt)~

    Có thể duy trì một biến max để tính tổng này

    void dfs(int u, int p=-1) {
    int sum = 0;
    for (int v...) {
    ...
    int ma = 0;
    for (int x=0; x<=f[v]; x++) cur = max(cur, dp[v][x] + x);
    sum += cur;
    }
    dp[u][1] = max(dp[u][1], sum);
}

    Xét đỉnh u màu đen

    Gọi ~f[u]~ là số đỉnh trắng tối đa của ~u~ có thể đi lên trên

    Khi xét đến đỉnh v là con của u, thì ~f[u]~ hiện tại sẽ lưu tổng của các ~f[v']~ với v' là con của u và nằm trước v.

    Gọi số đỉnh màu trắng trong các con trước v là cnt_1 và số đỉnh màu trắng trong cây con gốc v là cnt_2, thì số cặp màu trắng mới tạo ra sẽ tăng ~cnt_1 \times cnt_2~

    Ví dụ

    Trong hình này, trạng thái ~dp[u]~ đã tính tới các con trước v, nếu có ~cnt_1 = 3~ và ~cnt_2 = 4~ thì số cặp trắng đến được nhau là ~3 \times 4 = 12~

    Công thức

    $$dp[u][cnt_1+cnt_2] = max(dp[u][cnt_1+cnt_2], dp[u][cnt_1] + dp[v][cnt_2] + cnt_1 \times cnt_2)$$

    Công thức này có độ phức tạp thông thường là O(~n^3~), để tối ưu về độ phức tạp O(~n^2~), ta sẽ cài khéo một chút bằng thuật toán Knapsack trên cây.

    Code mẫu:

     void dfs(int u, int p=-1) {
     dp[u][0] = 0;
     for (int v:a[u]) if (p != v) {
         dfs(v, u);
         for (int cnt1=f[u]; cnt1>=0; x--)
             for (int cnt2=0; cnt2<=f[v]; cnt2++)
                 dp[u][cnt1+cnt2] = max(dp[u][cnt1+cnt2], dp[u][cnt1] + dp[v][cnt2] + cnt1*cnt2);
         f[u] += f[v];
     }
     f[u] = max(f[u], 1);
 }