Sub 1 / Sub2 :

Sub 1 : Với subtask này, nhận thấy số lượng cách điền màu là số cách phân hoạch n-1 cạnh thành k nhóm với các màu khác nhau, do đó với n=10 sẽ có không quá 21147 cách điền màu. Từ đó dễ ra được công thức đệ quy.

Sub 2 : Cải tiến từ sub 1 dùng nhánh cận. Xây dựng tô màu cạnh lần lượt theo thứ tự duyệt cây. Trong quá trình tô màu, nếu ta tô bằng màu trước đó, thì không nhất thiết kiểm tra tính hợp lệ của cây; ngược lại nếu ta một màu mới cho cạnh đó, ta kiểm tra các đường đi liên quan đến cạnh này. Đến khi tô hết các cạnh, ta sẽ có luôn thông tin số lượng màu phân biệt trên cây, vậy nên đơn giản cập nhật vào kết quả.

Sub 3 / Sub 4 / Sub 5 :

Sub 3 : Ta gọi dp[u][i][j] (i >= j) (i >= 0 && j >= 0) là số màu lớn nhất có thể tô được để đường đi dài nhất có màu khác nhau là i và đường đi dài nhì có màu khác nhau là j (màu trên đường của i với j phải khác nhau và đường đi phải từ gốc u ra)

Dễ thấy, một con u thỏa mãn khi i+j < k vì nếu ghép 2 đoạn đường kia lại thì sẽ ra được 1 đường có màu khác nhau và độ dài < k (các đường còn lại sẽ bé hơn 2 đường này ghép với nhau)

Hơn nữa, ta nhận ra rằng chỉ có thể có 1 đường có màu khác nhau là i vì nếu có 2 đường có độ dài i thì ta có thể ghép 2 đường đấy ra 1 đường độ dài i+i.

Có các trường hợp sau của các đỉnh con của u (gọi là v) (_dp khác dp ở chỗ nó lưu số màu lớn nhất và đoạn dài nhất <= i và dài nhì <= j):

1. Nếu cây con gốc v ko chứa con độ dài lớn nhất và cạnh (u,v) là một màu mới -> _dp[v][j-1][j-1] (nếu > j-1 thì ghép với cạnh (u,v) ra đường dài thứ 2 của u sẽ > j)
2. Nếu cây con gốc v ko chứa con độ dài lớn nhất và cạnh (u,v) là một màu cũ -> tối ưu là chọn màu ở trong đường dài nhất ở cây con gốc v - > _dp[v][k-1][j-1].
3. Nếu cây con gốc v chứa con độ dài lớn nhất và cạnh (u,v) là một màu mới -> _dp[v][i-1][i-1] (tương tự như trường hợp 1).
4. Nếu cây con gốc v chứa con độ dài lớn nhất và cạnh (u,v) là một màu cũ -> _dp[v][k-1][i-1] (tương tự như trường hợp 2).

Như đã chứng minh từ trước thì chỉ có 1 con gốc v sẽ chứa đường có độ dài lớn nhất -> For từng trường hợp của v

Từ đó ra công thức dp :

1. Nếu v ko phải con được chọn : dp[u][i][j] += max(_dp[v][j-1][j-1] + 1, _dp[v][k-1][j-1], _dp[v][i-1][i-1] (trường hợp này tức sẽ ko có đường toàn màu khác nhau chứa cạnh (u,v) )
2. Nếu v được chọn : dp[u][i] += max(_dp[v][i-1][i-1] + 1, _dp[v][k-1][i-1]);

Độ phức tạp O(n^2 * k^2)

Sub 4 :

Tương tự sub 3 nhưng thay thành dp[u][i][j][0/1] là đã chọn được v hoặc chưa chọn được v (sub này không quan trọng để làm sub cuối nên admin sẽ bỏ qua)

Độ phức tạp O(n * k^2 * 2)

Sub 5 :

Thay vì thử từng trường hợp v ta sẽ coi như tất cả đều ko được chọn rồi sẽ chọn con có thể tăng kết quả lên nhiều nhất

Gọi x = max(dp[v][j-1][j-1] + 1, _dp[v][k-1][j-1], _dp[v][i-1][i-1]) -> Nếu chọn v thì đáp án sẽ tăng lên là max(dp[v][i-1][i-1] + 1, _dp[v][k-1][i-1]) - x.

Với mỗi đỉnh gốc u ta sẽ lưu mảng opt[i][j] để lưu con v lớn nhất cho dp[u][i][j] rồi sau khi tính xong ta sẽ for từng cặp (i,j) để tăng lên

Độ phức tạp O(n * k^2)

Lưu ý : Sub cuối có thể gây tràn bộ nhớ nên có thể thay vì void dfs() t sẽ return mảng dp tại gốc u để các con cha của u sử dụng rồi xóa nó đi