Đầu tiên ta dựng cây centroid $T'$ của $T$, mỗi node $u$ trên cây $T'$ ta lưu các tổ tiên của nó trên $T'$ với các thông tin:$c,d,b$: centroid, distance, branch (node $c$ và khoảng cách từ $u$ đến $c$, branch là nhánh con chứa $u$ trên cây con gốc $c$ ở $T'$ để xử lí việc cộng thừa)
Tiếp tục mỗi node $u$ trên cây centroid $T'$ ta một số cây BIT:
- Cây thứ nhất để lưu tổng các giá trị ở cây con gốc $u$ trên $T'$ tương ứng với khoảng cách từ $u$ trên $T$.
- Các cây BIT khác tương ứng với mỗi nhánh con của cây con gốc $u$.
Khi đó, mỗi truy vấn $(u,k)$ ta sẽ đi từ $u$ lên các tổ tiên $p$ ở trên cây centroid và cộng vào đáp án tổng giá trị các đỉnh cách $p$ là không quá $k-d$ cạnh với $d$ là khoảng cách từ $u$ đến $p$ trên $T$.
Tuy nhiên, khi đó ta bị cộng thừa một số đỉnh đã được cộng ở trước và một số đỉnh không có LCA với $u$ là $p$, khi đó ta tìm nhánh con $b$ chứa $u$ của cây con gốc $p$ trên $T'$ và trừ đi các đỉnh có khoảng cách không quá $k-d$ với $p$.
Khi update ta làm tương tự, đi lên từ $u$ trên cây $T'$ và update các tổ tiên và nhánh con tương ứng.
nai0610
Created at
1 likes