Centroid và một số bài toán nhỏ

Centroid và một số bài toán nhỏ

* Khi giải thuật n*n --> nlogn

Đây là một giải thuật khá hữu dụng để xử lí các bài toán về cây mà mình mới học được, và có sự tham khảo rất lớn từ:

+ https://threads-iiith.quora.com/Centroid-Decomposition-of-a-Tree

+ http://www.geeksforgeeks.org/centroid-decomposition-of-tree/

Bài toán truy vấn 2: Truy vấn trên đồ thị

Sau đây mình xin trình bày một số bài toán có sử dụng truy vấn trên đồ thị 

Bài toán 1: Cho n đỉnh, và n-1 giai đoạn. Giai đoạn i cho phép ta liên kết đỉnh i+1 à với 1 đỉnh nào đấy(<i) . Ban đầu có đỉnh 1. Bài toán đặt ra: Với mỗi giai đoạn, hãy tìm khoảng cách xa nhất giữa 2 đinh bất kì.