110 選手班 - 樹論

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

#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

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) ;
}

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

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

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

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;
}