Tree

UVa 1479. Graph and Queries

Description 給定一張無向圖，有三種操作： D x ：刪除第x條邊 Q x y ：查詢x所在集合裡面第y大的數字，若查詢失敗，則此次查詢的結果為0 C x y ：將第x點的值改成y 最後輸出所有查詢的平均值。

Template. Heavy-light Decomposition

第一次DFS，son()：先紀錄所有點的子節點（含）數目、深度等資訊。 第二次DFS，build()：依據上次DFS的結果，優先選擇子節點最多的點構成重鏈。

Template. LCA Doubling Search

使用倍增法的做法來計算LCA。 先製作dp表，$dp[i][j]$代表$i$的第$2^j$祖先是誰，若不存在則為-1。 在查詢時，先將點$a$和$b$調整到相同高度，再一起慢慢往上移動尋找LCA。 時間複雜度：$O(N log N)$