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/

1.Centroid là gì ? 

Centroid của cây là một nút nào đó sao cho sau khi cắt bỏ nút đó đi thì các cây con còn lại có kích thước <= n/2

Ví dụ : như hình trên thì nút 8 là 1 centroid , sau khỉ bỏ nút 8 thì có 2 cây con và mỗi cây con có kích thước lần lượt là 7. <= 17/2
Ngoài ra việc tiến hành tìm centroid của các cây con, sau đó lấy chúng làm centroid của cây ban đầu , ta dựng được 1 cây mới là cây centroid

Sau khi dựng lại cây :

2.Làm sao để tìm centroid:
 Người ta chứng minh được rằng một cây đều có ít nhất 1 centroid .
Do đó ta có 1 giải thuật đơn giản sau:
+ Chọn 1 nút bất kì u . Kiểm tra xem nó có là centroid không.Nếu đúng thì return u
+ Nếu không thì chắc chắn centroid sẽ thuộc cây con mà có kích thước >N/2. tìm kiếm trong cây con đấy.
Code:

Hàm dfs() để chuẩn bị đếm số con
Hàm find_ct() tiến hành tìm centroid .

Xây cây centroid cũng tương tự

3.Tính chất cơ bản của centroid
+ (1)Việc dựng lại cây centroid có độ phức tạp O(nlog(n)) với n là số nút của cây
+ (2) Độ cao tối đa của cây cetroid là log(n) ( trường hợp tốt nhất là cây nhị phân cân bằng)
+ (3) hai nút đường đi từ u --> v cũng bao gồm lca(u,v)
+ Khoảng cách giữa 2 nút trong cây centroid mới không phải là khoảng cách trong cây cũ
4.Một số dạng bài tập về centroid
Trong quá trình học, mình thấy có 2 kiểu giải khá là "chuẩn" thông qua centroid
+ (2) + (3) --> để đưa về cây centroid để quy hoạch động trên cây centroid
+ Dùng tính chất " bắt buộc đi qua" + centroid để đưa bài toán từ n*n --> nlogn
Sau đây là 1 số bài tập
4,1 Xenia and tree
Link : http://codeforces.com/contest/342/problem/E

Gọi ans[i] là khoảng cách nhỏ nhất giữa nút i và 1 nút đỏ
Khi tô màu nút i --> màu đỏ . ta cập nhật lên các tổ tiên của nó (tạm gọi là x)
ans[x] = min (ans[x] , dis(i,x) )  (ans[i] = 0)
Khi truy vấn theo (3) ta chỉ cần get với các tổ tiên của nó thôi
res = min (res, ans[x] + dis(x,i))
Ta có giải thuật O(nlogn^2)

Nhận xét : với dạng như trên ta có thể đưa về cây centroid và qhđ trên cây bình thường, ngoài ra còn có thể áp dụng nhiều thuật toán khác nữa .
Một số bài tập liên quan :
+ http://www.spoj.com/problems/QTREE5/
+ https://www.hackerrank.com/challenges/bst-maintenance

4.2:  Tree query
Link : http://codeforces.com/gym/100570/problem/F

Ta sẽ giải quyết truy vấn offline bằng cách giải quyết tất cả các truy vấn cho 1 nút cùng 1 lúc
Ta sẽ cây centroid và với mỗi centroid ta sẽ giải quyết :
+ Các truy vấn của centroid đó bằng cách : đếm số các số thỏa mãn ( ta có thể đưa vào mảng rồi chặt nhị phân ) .  độ phức tạp sẽ là O ( là số truy vấn * logn + số nút chưa là centroid * logn )
ans[id] = upper_bound(add.begin(),add.end(),w)-add.begin()-1;
Với w là trọng số của truy vấn, id là số truy vấn
+ Ta cập nhật kết quả cho các truy vấn có thể đi qua nút đó ta làm tương tự truy vấn. Việc này mất
nlog(n) .
Tính sơ sơ thuật toán có độ phức tạp là n*nlog(n) nhưng có sự kì diệu vô cùng nên thuật toán đã giảm xuống O(nlog(n)^2)

Một số bài tập tương tự :
+ http://codeforces.com/contest/321/problem/C
+ https://www.codechef.com/problems/PRIMEDST
+ http://codeforces.com/problemset/problem/715/C

Dưới đây là 1 số dạng mà mình nắm bắt được, tuy không nhiều nhưng giúp ta giải được 1 số bài toán về cây, Hy vọng các bạn ưu thích bài viết này @@