Phân tích: Rainbow Trees

Chọn bất kỳ đỉnh \(r\) nào làm gốc. Chúng ta xem cây như được bắt gốc tại \(r\), và — như thường lệ — vẽ cây với gốc ở trên cùng, các nút ở độ sâu \(d\) nằm trên cùng một mức, cách gốc \(d\) đơn vị.

Bằng cách tô màu một phần trên một tập hợp con các cạnh, chúng ta ám chỉ việc gán màu cho các cạnh trong tập hợp con đó sao cho điều kiện "tô màu cầu vồng" được thỏa mãn trên tập hợp con đó. Chúng ta không quan tâm đến việc tô màu các cạnh không nằm trong tập hợp con này.

Với mỗi nút \(x\), chúng ta định nghĩa giá trị:

\(f(x)\) := số cách tô màu cây con bắt gốc tại \(x\), với một cách tô màu một phần bất kỳ cho tập các cạnh kề với cha của \(x\).

Việc \(f(x)\) được xác định duy nhất không phải là điều hiển nhiên. (Tại sao con số này luôn giống nhau đối với bất kỳ cách tô màu một phần nào đã cho?). Để thấy rằng \(f(x)\) thực sự được xác định rõ ràng, hãy xem xét một thuật toán để tính toán nó.

Giả sử \(z\) là cha của \(x\), và bậc của \(z\) là \(D\). Lưu ý rằng ràng buộc cầu vồng là một điều kiện mang tính địa phương — màu của bất kỳ cạnh nào khác ngoài những cạnh kề với \(z\) đều không ảnh hưởng đến việc tô màu cho cây con bắt gốc tại \(x\).

Giả sử \(x\) có \(t\) nút con — \(y_1, y_2, \dots, y_t\). Để tô màu tất cả các cạnh trong cây con bắt gốc tại \(x\), chúng ta thực hiện như sau:

• Tô màu cạnh \(x y_1\). Có \(k - D\) lựa chọn, vì cạnh này không thể có cùng màu với bất kỳ cạnh nào trong số \(D\) cạnh kề với \(z\), và không có cạnh nào khác trong phần đã tô màu gây ra ràng buộc lên nó.
• Tô màu cạnh \(x y_2\). Có \(k - D - 1\) lựa chọn, vì cạnh này không thể có cùng màu với bất kỳ cạnh nào trong số \(D\) cạnh như trên, cũng như không được trùng màu với \(x y_1\).
• ...
• Tô màu cạnh \(x y_t\). Có \(k - D - t + 1\) lựa chọn.
• Bây giờ chúng ta đã có một cách tô màu một phần mà tất cả các cạnh kề với \(x\) đều đã được tô màu. Chúng ta tô màu cây con bắt gốc tại \(y_1\). Có \(f(y_1)\) cách.
• ...
• Có \(f(y_t)\) cách để tô màu cây con bắt gốc tại \(y_t\).

Thật vậy, việc tính toán chỉ phụ thuộc vào \(D\), bậc của cha của \(x\). \(f(x)\) là tích của các số nêu trên.

Không có gì quá đặc biệt về gốc \(r\), ngoại trừ việc chúng ta cần quy ước \(D = 0\) trong trường hợp đó. Và lời giải cho bài toán của chúng ta chính là \(f(r)\).

Độ phức tạp

Với mỗi nút, chúng ta duyệt qua các nút con của nó và thực hiện các phép nhân. Tổng số lần thực hiện các phép tính là tuyến tính theo số lượng nút \(n\). Độ phức tạp thời gian là \(O(n)\).

Dựa trên phân tích chính thức của Google Code Jam.