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\)
1. 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





























#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
















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













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

Move lower one to the same level
- let \(y\) be the depth difference
- convert \(y\) into binary
- jump through \(lca[x][i]\)
Binary Search the highest point where \(u\), \(v\) don't meet
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

































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



































































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

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`	在筆記中貼入程式碼
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.

110 選手班 - 樹論

tags: 宜中資訊 CP

Outline

Diameter

Problem

Solution I

Proof

Implementation

Solution II

Advance

Centroid

Problem

Properties

Solution

Implementation

Euler Tour Tree

Solution

Properties

Application

Implementation

Euler Tour on Edge

Lowest Common Ancestor

Problem

Naive

Solution I

Build

LCA

Implementation

Solution II

Heavy-Light Decomposition

Problem

Solution

Implementation

Credit

tags: `宜中資訊` `CP`