Ta mặc định các nút đen/trắng trong lời giải là các nút không phải lá.

Subtask 1: ~1 \leq n \leq 10~

Ta sinh tất cả hoán vị có thể cho các nút lá, sau đó dùng DP trên cây để tính toán với công thức như sau: Gọi ~p[u]~ là giá trị nút lá ~u~ sau khi sinh hoán vị, ~f[u]~ là giá trị của nút ~u~.

• ~f[u] = p[u]~ nếu ~u~ là lá.
• ~f[u] = \max(f[v])~ ~\forall v \in child(u)~ nếu ~u~ là nút đen.
• ~f[u] = \min(f[v])~ ~\forall v \in child(u)~ nếu ~u~ là nút trắng

Subtask 2: ~1 \leq n \leq 10^6~

Nhận xét: Nếu tồn tại một cách gán nhãn sao cho đáp án lớn hơn bằng ~X~, thì chắc chắn tồn tại cách gán sao cho đáp án lớn hơn bằng ~X - 1~.

Gọi ~f[u]~ là số lượng giá trị ~\geq X~ cần gán vào các nút lá thuộc cây con gốc ~u~, sao cho giá trị của nút ~u~ cũng ~\geq X~.

Ta sử dụng chia nhị phân kết quả để tìm ~X~ và thực hiện DP trên cây theo công thức sau:

• ~f[u] = 1~ với ~u~ là nút lá.
• ~f[u] = \max(f[v])~ ~\forall v \in child(u)~ nếu ~u~ là nút đen.
• ~f[u] = \sum\limits_{v \in child(u)} f[v]~ nếu ~u~ là nút trắng.

Nếu ~f[1] \leq k - X + 1~ thì ta có đủ giá trị ~\geq X~ để làm cho nút ~1~ có giá trị ~\geq X~.

Độ phức tạp: ~O(n.log_2n)~.

Tối ưu: Từ hàm chia nhị phân trên, ta nhận thấy ~X~ phải thỏa mãn bất đẳng thức sau ~X \leq k - f[1] + 1~. Do đó để nút ~1~ đạt ~\max~ thì ~X~ phải đạt ~\max~, hay nói cách khác ~X = k - f[1] + 1~. Độ phức tạp: ~O(n)~.

Code tham khảo:

void dfs(int u) {
    if (isLeaf[u]) f[u] = 1;
    else f[u] = (color[u] == 0 ? 0 : inf);
    for(int v : G[u]) {
        dfs(v);
        if (color[u] == 0) f[u] += f[v];
        else minimize(f[u], f[v]);
    }
}