Solutions of Line tree

Select solution language

nai0610 Created at 2 likes

Ban đầu, DFS từ đỉnh gốc $1$ để tính Euler tour và mảng nâng nhị phân. Ở đây ta xét các mối quan hệ cha con trong cây gốc $1$. Xét một truy vấn $2 \ u \ x$ và gốc cây hiện tại là $r$, ta có $3$ trường hợp: - Trường hợp 1: $u=r$, ta chỉ việc trả lời đáp án khi xét mọi đỉnh của cây. - Trường hợp 2: $u$ không là tổ tiên của $r$, dễ thấy kết quả chính là max của các đường thẳng của các node trên cây con gốc $u$ tức đoạn $[tin_u,tout_u]$. - Trường hợp 3: $u$ là tổ tiên của $r$: Gọi $d$ là khoảng cách từ $u$ đến $r$, $v$ là tổ tiên thứ $d-1$ của $r$, tức là đỉnh kề $u$ trên đường đi từ $r$ đến $u$, khi đó tập các node trong cây con gốc $u$ khi $r$ là gốc chính là tập các đỉnh không thuộc cây con gốc $v$, hay tập $[1,tin_v-1]\ \cup [tin_v+1,n]$. Từ đây ta có thể dễ dàng trả lời các truy vấn bằng một Segment Tree lưu các bao lồi. Độ phức tạp nếu dùng LineContainer là $O(1)$ mỗi truy vấn $1$ và $O(log^2n)$ mỗi truy vấn $2$.