<style> .reveal .slides { text-align: left; } </style> # LCA and Euler Tour Technique Competitive programming 2 2021/12/06 ---- - 最近共同祖先(Lowest Common Ancestor) ###### (先備知識-DFS) - 樹壓平 ###### (先備知識-DFS/線段樹) --- ## 最近共同祖先 ### (Lowest Common Ancestor) <div style="font-size:25px"> 最近公共祖先是指在一個有根樹中同時擁有 $v$ 和 $w$ 作為後代的最深的節點 如果 $v$ 是 $w$ 的後代，則 $w$ 就是 $v$ 和 $w$ 的最近共同祖先 </div> ----  以這棵樹為例，假設根節點為1: 5 跟 6 的 lca 為 2 1 跟 7 的 lca 為 1 7 跟 8 的 lca 為 4 5 跟 4 的 lca 為 1 ---- ### Binary Lifting Approach ---- <div class="text2"> * 預處理 <div style="position: absolute; left: 70%; top:70%;">  </div> >先把每個節點的一倍祖先，二倍祖先，四倍祖先 ... $2^n$ 倍祖先預先建好 >每個節點建 $lgN個$ >當輩分太高時( $2^x$ 倍祖先超出根節點)，則將 $2^x$ 倍祖先設為根結點 | |1倍祖先|2倍祖先|4倍祖先| | ------ | ---- | ---- | ---- | | node1 | 1 | 1 | 1 | | node2 | 1 | 1 | 1 | | node3 | 1 | 1 | 1 | | node4 | 3 | 1 | 1 | | . | | . | | . | </div> ---- <div class="text2"> * 詢問 >假設詢問的點個點為$x,y$ > >先判斷兩者是否為互相的祖先 >可以利用進入及離開的時間做判斷 >如其中一個點 $x$ 為另一個點 $y$ 的祖先則 LCA 為 $x$ >反之則為 $y$ > >若彼此都不是祖先關係，則我們用二分搜的方式先找出x的祖先中最靠近根結點的非y的祖先 </div> ---- <div class="text2"> > >以這張圖為例 >假設 $x$ 為6, $y$ 為8，則 $x$ 的祖先中最靠近根節點的但非 $y$ 的祖先為2 >$x$ 為7, $y$ 為8，則 $x$ 的祖先中最靠近根節點的但非 $y$ 的祖先為7 >$x$ 為8, $y$ 為5，則 $x$ 的祖先中最靠近根節點的但非 $y$ 的祖先為3 </div> ---- <div class="text2"> >假設我們選詢問點 $x$，從 $x$ 的最高倍祖先開始判斷，判斷 $x$ 的最高倍祖先是否同為$y$的祖先 >若不是 $y$ 的祖先節點，則將 $x$ 設為 $x$ 的最高倍祖先 >接著重複做一樣的事判斷 $x$ 的次高倍, $x$ 的次次高倍.... $x$ 的兩倍, $x$ 的一倍祖先 >只要能往上跳就把 $x$ 往上移動，保證最後一定能走到 $x$ 的祖先中非 $y$ 的祖先最靠近根結點的節點 >而找到此節點，則此節點的父節點即為 LCA > </div> ---- sample code ```cpp= //build void build(int node,int fatherNode){ for(int i=0;i<__lg(n);i++){ anc[node][i]=fatherNode; fatherNode=anc[fatherNode][i]; } } void dfs(int node,int fatherNode){ dfsTimeIn[node]=ti++; build(node,fatherNode); for(int i=0;i<Graph[node].size();i++){ if(Graph[node][i]==fatherNode) continue; dfs(Graph[node][i],node); } dfsTimeOut[node]=ti++; } ``` ---- sample code ```cpp= //query bool isAncestor(int x,int y){ return dfsTimeIn[x]<=dfsTimeIn[y]&& dfsTimeOut[x]>=dfsTimeOut[y]; } int query(int x,int y){ if(isAncestor(x,y)) return x; if(isAncestor(y,x)) return y; for(int i=__lg(n)-1;i>=0;i--){ if(!isAncestor(anc[x][i],y)) x=anc[x][i]; } return anc[x][0]; } ``` ---- ### 複雜度分析 <div class="text1"> * 預處理 >每個節點建一倍祖先，二倍祖先，四倍祖先，...，$2^{lgN}$倍祖先 >總共$NlgN$個，每個建立為O(1) >複雜度為 $O(NlgN)$ * 詢問 >每筆詢問則是在樹上二分搜，找非共同祖先中最靠近根節點的節點 >每次詢問$O(lgN)$ </div> --- ## 樹壓平 ### LCA and Euler Tour Technique <div style="font-size:25px"> 子樹詢問、修改 EX：有一棵樹$N$個節點，節點上只會有$0,1$兩種點權， 兩種操作 1. 每次詢問某個點的子樹中有幾個1 2. 修改以某個點的子樹，將權重為0的改成1,1的改成0 </div> ---- 作法 $Q$筆詢問，每次$O(N)$修改 複雜度$O(QN)$...太慢了 因此我們要把樹壓平 ----  紀錄每個點dfs時進入的時間 node | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ---- | - | - | - | - | - | - | - | - | dfs time| 1 | 2 | 8 | 3 | 4 | 5 | 6 | 7 | ----  <div style="font-size:25px; text-align:left; margin-left:31%"> 而每個點的子樹，dfs順序必定會是連續的 EX: - 5的子樹dfs順序為4-7之間 - 2的子樹dfs順序為2-7之間 - 1的子樹dfs順序為1-8之間 因此我們把每個點的子樹區間記錄起來， 就可以用線段樹之類的資料結構維護 </div> ---- <div style="font-size:25px; text-align:left; margin-left:31%">  EX: - 修改5的子樹修改區間4-7 - 詢問2的子樹詢問區間2-7 </div> ---- 紀錄子樹區間 <div style="margin-left:-180px"> ```cpp= int ti=0; vector<pair<int,int>> dfsTime(n); int dfs(int x,int f){ dfsTime[x].first=dfsTime[x].second=ti++; for(auto i:edge[x]){ if(i==f) continue; dfsTime[x].second=max(dfsTime[x].second, dfs(i,x)); //紀錄最右界 } return dfsTime[x].second; } ``` </div> ---- <div style="font-size:25px"> 用資料結構維護後，單次詢問/修改的複雜度 就從原本的$O(N)$降成O$(lgN)$ AC! </div> ---- ### 用樹壓平求LCA  | time | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |11 |12 |13 | | ----- | - | - | - | - | - | - | - | - | - | - | - | - | - | | node | A | B | C | D | C | E | F | E | C | B | A | G | A | | depth | 1 | 2 | 3 | 4 | 3 | 4 | 5 | 4 | 3 | 2 | 1 | 2 | 1 | ----  LCA(D,F) = C | time | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |11 |12 |13 | | ----- | - | - | - | - | - | - | - | - | - | - | - | - | - | | node | A | B | C |[D | C | E | F]| E | C | B | A | G | A | | depth | 1 | 2 | 3 | 4 | 3 | 4 | 5 | 4 | 3 | 2 | 1 | 2 | 1 | ---- 求出 u, v 的LCA為區間內的最小深度的點  | time | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |11 |12 |13 | | ----- | - | - | - | - | - | - | - | - | - | - | - | - | - | | node | A | B | C | D | C | E | F | E | C | B | A | G | A | | depth | 1 | 2 | 3 | 4 | 3 | 4 | 5 | 4 | 3 | 2 | 1 | 2 | 1 | ---- 記錄每個點的進來時間與離開時間 ```cpp= int ti = 0; //時間戳記 void dfs(int x,int f,int d){ dep[ti] = d; //記錄在當下時間點的節點深度 node[ti] = x; //記錄在當下時間點的節點 tin[x] = ti++; //紀錄點x進入時間點 for(auto i:edge[x]){ if(i != f) dfs(i,x,d+1); } dep[ti] = d; //記錄在當下時間點的節點深度 node[ti] = x; //記錄在當下時間點的節點 tout[x] = ti++; //紀錄點x離開時間點 } ``` ---- 因此可以用線段樹等資料結構求LCA ```cpp= int query(int u, int v){ if(tin[u] > tin[v]) swap(u, v); return segmentTree.query(tout[u], tin[v]); } ``` --- ### Question Time and Practice [Homework Link](https://vjudge.net/contest/472126) <div style="font-size: 30px"> 提交期限到下星期一 12/13 23:59 截止 </div> ---- ### 額外加分 <div style="font-size: 30px"> 由於這幾年ICPC題目的趨勢越來越CF 今天開始的codeforces, atcoder round個人積分賽 有參加有額外加分(要rated才算) 如有參加須賽後補題 </div> <style> .text1{ font-size:30px; text-align:left; } .text2{ font-size:20px; text-align:left; } </style>