# 110 選手班 - 樹論 ###### tags: `宜中資訊` `CP` Ccucumber12 2021.08.09 --- ## Outline - Diameter - Centroid - Euler Tour Tree - Lowest Common Ancestor - Heavy-Light Decomposition --- ## Diameter ---- ### Problem - Given A Tree $G$ - Find the longest path on $G$ - Time Complexity $O(N)$ ---- ### Solution I - 1. DFS on abitrary point and find the farthest point $S$ - 2. DFS on $S$ and find the farthest point $T$ - $path(S,T)$ is the diameter - two DFS $\rightarrow O(N)$ ---- #### Proof - let diameter be $\delta(S,T)$ - discuss start point $x$ in two situations: - $x$ in $\delta(S,T)$ - $x$ not in $\delta(S,T)$ ---- $x$ in $\delta(S,T)$ - if farthest point $z$ in 1.DFS is not $S$ or $T$ - $\implies \delta(x,z) > \delta(x,S)$ - $\implies \delta(x,z) + \delta(x,T) > \delta(x,S) + \delta(x,T)$ - $\implies \delta(z,T) > \delta(S,T) \Rightarrow\Leftarrow$ ---- $x$ not in $\delta(S,T)$ for farthest point $z$ in 1. DFS, discuss two situations: - $\delta(x,z)$ cross $\delta(S,T)$ - $\delta(x,z)$ not cross $\delta(S,T)$ ---- $\delta(x,z)$ cross $\delta(S,T)$ at $y$ - $\because z$ is farthest point and not $S$ or $T$ - $\therefore \delta(y,z) > \delta(y,S)$ - $\implies \delta(y,z) + \delta(y,T) > \delta(y,S) + \delta(y, T)$ - $\implies \delta(z,T) > \delta(S,T) \Rightarrow\Leftarrow$ ---- $\delta(x,z)$ not cross $\delta(S,T)$ - let $y$ be first point from $x$ to $S$ in $\delta(S,T)$ - let $y'$ be the first point from $y$ to $z$ in $\delta(x,z)$ - $\because \delta(S,T)$ is diameter and $z$ is not $S$ or $T$ - $\therefore \delta(y,S) \geq \delta(y,z)$ - $\implies \delta(y',y) + \delta(y,S) > \delta(y', z) \Rightarrow\Leftarrow$ ---- - $z$ has to be $S$ or $T$ - $2$. DFS must find the other endpoint by definition ---- #### Implementation ```c= #include <bits/stdc++.h> using namespace std ; vector<int> g[100010] ; int lev[100010], tar ; void dfs(int x, int p) { lev[x] = lev[p] + 1 ; if(lev[x] > lev[tar]) tar = x ; for(auto i:g[x]) if(i != p) dfs(i, x) ; } int main() { int n; // input g for(int i=1; i<=n; ++i) lev[i] = 0 ; dfs(1, 0) ; for(int i=1; i<=n; ++i) lev[i] = 0 ; int S = tar ; dfs(S, 0) ; int T = tar ; cout << S << ' ' << T << endl ; } ``` ---- ### Solution II - DP - find an arbitrary vertex as root - maintain $d_1$ and $d_2$ for every vertex - $d_1$: farthest descendent - $d_2$: second farthest descendent - $\delta(S,T) = d_1[LCA(S,T)] + d_2[LCA(S,T)]$ ---- - $\forall i$ is $x$ child: - $d_1[x] = max(d_1[i] + 1)$ - $d_2[x] = max(d_2[i] + 1, d_1[i] + 1$ where $d_1[i] + 1$ is not $d_1[x])$ - done by DFS + DP - $O(N)$ ---- ### Advance - Negative edge - Second Diameter --- ## Centroid ---- ### Problem - Given a tree $G$ - find the point $g$ S.T. - $max(|g \rightarrow subtree|)$ is smallest ---- ### Properties - at most two possible $g$, and they are adjacent - $max(|g \rightarrow subtree|) \leq |G|/2$ - $\sum(\delta(i,g))$ is smallest - if combine two trees, the new $g'$ will be in $\delta(g_1, g_2)$ - remove/add a new vertex, $g$ will move at most one edge ---- ### Solution - By property 1 and 2 - DFS through the tree - calculate $max(|x \rightarrow subtree|)$ - $O(N)$ ---- - $max(|x \rightarrow subtree|)=$ - $\forall i$ is $x$ child: $max(|subtree(i)|)$ - $|G| - \sum|subtree(i)| - 1$ - below and above ---- ### Implementation ```c= vector<int> g[100010] ; int sz[100010], n; vector<int> cen ; void dfs(int x, int p) { sz[x] = 1 ; int ret = 0 ; for(auto i:g[x]) if(i != p) { dfs(i, x) ; sz[x] += sz[i] ; ret = max(ret, sz[i]) ; } ret = max(ret, n - sz[x]) ; if(ret * 2 <= n) cen.push_back(x) ; } ``` --- ## Euler Tour Tree ----  ---- ### Solution - DFS on a rooted tree - mark the nodes when enters and leaves - $O(N)$ ---- ### Properties - Every subtree is a interval - Turn tree problem into sequence problems - Use data structures to optimize ---- ### Application - LCA $\Rightarrow$ RMQ on Euler sequence - Add a subtree $\Rightarrow$ Insert an interval - Remove a subtree $\Rightarrow$ Remove an interval - Change root $\Rightarrow$ Rotate Euler sequence ---- ### Implementation ```c= vector<int> g[100010] ; vector<int> et ; int in[100010], out[100010] ; void dfs(int x, int p) { et.push_back(x) ; in[x] = et.size() - 1 ; for(auto i:g[x]) if(i != p) { dfs(i, x) ; et.push_back(x) ; } out[x] = et.size() - 1 ; } ``` ---- ### Euler Tour on Edge  ---- - DFS on rooted tree - downwards: positive - upwards: negative - $O(E)$ ---- - calculate $path(S,T)$ - let $x=LCA(S,T)$ - $path(S,T)=[x,S] + [x,T]$ - prefix sum --- ## Lowest Common Ancestor ---- ### Problem - Given a rooted tree $G$ - find the lowest common root of $u$, $v$ - $O(log\ N)$ / query ---- ### Naive - going up at the lower point - until they meet each other - $O(h)$ ---- ### Solution I - Reduce the time to jump upwards - Binary lifting (Sparse table) - maintain the $2^i$ ancestor of each point ---- #### Build - $lca[x][i] = x \rightarrow 2^i\ ancestor$ - $lca[x][0] = fa[x]$ - $lca[x][i] = lca[lca[x][i-1]][i-1]$ ---- - DFS: $O(N)$ - DP: $O(NlogN)$ - Total: $O(NlogN)$ ---- #### LCA 1. Move lower one to the same level - let $y$ be the depth difference - convert $y$ into binary - jump through $lca[x][i]$ 2. Binary Search the highest point where $u$, $v$ don't meet 3. Father of that point is $LCA(u,v)$ ---- - Move to same level: $O(log\ N)$ - Binary Search: $O(log\ N)$ - Total: $O(log\ N)$ ---- #### Implementation ```c= vector<int> g[100010] ; int lca[30][100010] ; int lev[100010] ; void dfs(int x, int p) { lca[0][x] = p ; lev[x] = lev[p] + 1 ; for(auto i:g[x]) if(i != p) dfs(i, x) ; } void build(int n) { for(int i=1; i<=log2(n); ++i) for(int j=1; j<=n; ++j) lca[i][j] = lca[i-1][lca[i-1][j]] ; } int query(int a, int b) { if(lev[a] < lev[b]) swap(a, b) ; for(int i=25; i>=0; --i) if(lev[lca[i][a]] >= lev[b]) a = lca[i][a] ; if(a == b) return a ; for(int i=25; i>=0; --i) { if(lca[i][a] != lca[i][b]) { a = lca[i][a] ; b = lca[i][b] ; } } return lca[0][a] ; } ``` ---- ### Solution II - Do Euler Tour Tree - maintain $pos(x)$ which is the first time $x$ appears in Euler sequence - $LCA(u,v)=min[pos(u), pos(v)]$ ---- - Euler Tour: $O(N)$ - RMQ: Sparse Table - Build: $O(NlogN)$ - Query: $O(1)$ --- ## Heavy-Light Decomposition ---- ### Problem - Path problems on Trees - with modify and query - ex. dynamic path sum/max/min ---- ### Solution - Separate the tree into sequences to fit in DS - Time Complexity: $O($sequences$) \times O(DS)$ - $\implies$ minimum sequence for every path - $\implies$ Heavy-Light Decomposition (HLD) ---- - Heavy Edge: edge to max subtree - Light Edge: Every other edges - Connect vertex through Heavy Edges - $\implies$ every time switch a sequence, the size multiplies by two at least - $\implies$ switch at most $O(log\ N)$ sequences - Time complexity: $O(log\ N) \times O(DS)$ ----  ---- ### Implementation ```c= const int MXN = 200000; const int N = MXN + 10; struct info{ int w; int dep, pa, size, next; int id, root; // id on data structure } inf[N]; vec<int> g[N]; int prepare(int v, int pa, int d=0){ // find : dep, pa, size, next int maxsub = 0; inf[v].pa = pa; inf[v].dep = d; inf[v].size = 1; inf[v].next = -1; for(auto i:g[v]){ if(i == pa) continue; int sub = prepare(i, v, d+1); inf[v].size += sub; if(sub > maxsub) { maxsub = sub; inf[v].next = i; } } return inf[v].size; } int cntID = 1; void mapTo(int v, int pa, int root){ // map : id, root inf[v].id = cntID++; inf[v].root = root; modify(inf[v].id, inf[v].w); if(inf[v].next != -1) mapTo(inf[v].next, v, root); for(auto i:g[v]){ if(i == pa) continue; if(i == inf[v].next) continue; mapTo(i, v, i); } } void update(int x, int v){ inf[x].w = v; modify(inf[x].id, inf[x].w); } int query(int s, int t){ int ans = 0; while(inf[s].root != inf[t].root){ if(inf[inf[s].root].dep < inf[inf[t].root].dep) swap(s, t); amax(ans, DSquery(inf[s].id, inf[inf[s].root].id)); s = inf[inf[s].root].pa; } amax(ans, DSquery(inf[s].id, inf[t].id)); return ans; } ``` --- ## Credit - 演算法筆記 - OI wiki - https://www.chegg.com/homework-help/questions-and-answers/euler-tour-graph-path-traverses-edge-exactly--context-tree-say-edge-bidirectional-euler-to-q60792427