Cây cân bằng

Lời giải: Cây cân bằng

Hướng tiếp cận

Phân rã centroid kết hợp với matching đường đi qua centroid để tìm độ lồng tối đa.

Nhận xét quan trọng

1. Với mỗi centroid $c$, xét các đường đi $u\dots c\dots v$ ($u$, $v$ ở hai cây con khác nhau).
2. Phần trái ($c\to u$, không tính nhãn $c$): ${\text{sum}}_L$, ${\text{fmax}}_L$, ${\text{fmin}}_L$ (prefix sum trên đoạn $c\to u$, bắt đầu từ 0).
   • Hợp lệ: ${\text{fmax}}_L={\text{sum}}_L$ (tức $u$ đạt max trên đường đi).
3. Phần phải ($c\to v$, không tính nhãn $c$): ${\text{sum}}_R$, ${\text{fmin}}_R$.
   • Hợp lệ: ${\text{fmin}}_R={\text{sum}}_R$ (tức $v$ đạt min).
4. Cân bằng: ${\text{sum}}_L+{\text{sum}}_R=-\text{val}[c]$.
5. Độ lồng = ${\text{sum}}_L+max(-{\text{fmin}}_L,\text{val}[c]+{\text{fmax}}_R)$.

Thuật toán

1. Xử lý từng centroid $c$: khởi tạo pool với "nửa rỗng" (kết thúc tại $c$).
2. Với mỗi cây con của $c$: match đường đi mới với pool → cập nhật đáp án → thêm vào pool.
3. Đệ quy vào các cây con.

Độ phức tạp

• Thời gian: $O(N\log N)$
• Bộ nhớ: $O(N\log N)$