# 樹論
- [235. Lowest Common Ancestor of a Binary Search Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/submissions/)
- [236. Lowest Common Ancestor of a Binary Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/)

## LCA 最近共同祖先
- 例題 : [Kattis – Boxes](https://yuihuang.com/kattis-boxes/)
- 先 `O(nlogn)` 建立 dp[x][i] ，代表節點 x 往上走 2^i 部的節點
- dp[x][i] = dp[dp[x][i-1]][i-1]
- 可以 `O(logn)` 查詢任意點的任意倍祖先
- 給定兩個節點 u, v，可以 `O(logn)` 找出 LCA

#include <bits/stdc++.h>
using namespace std;

vector <int> G[1000];
int dp[1000][20], lvl[1000];
 
void dfs(int now, int p){
    lvl[now] = ~p ? lvl[p] + 1 : 0;
    dp[now][0] = p;
    for(int i = 1; (1<<i) <= lvl[now]; i++)
        dp[now][i] = dp[dp[now][i-1]][i-1];
    
    for(auto &nb:G[now]){
        if(nb==p)   continue;
        dfs(nb, now);
    }
}
 
int lca(int u, int v){
    if (lvl[u] > lvl[v]) swap(u, v);
    
    int dif = lvl[v] - lvl[u];
    for (int i = 0; i < 20; i++){
        if (dif & 1) v = dp[v][i];
        dif >>= 1;
    }
    if (u == v) return u;   // special case
    for (int i = 19; i >= 0; i--){
        if (dp[u][i] != dp[v][i]){
            u = dp[u][i];
            v = dp[v][i];
        }
    }
    return dp[u][0];        // one step away from LCA
}


int main(){
    vector<vector<int>> input = {{0,1},{0,2},{1,3},{1,4},{3,5},{4,6},{6,7},{2,8},{2,9},{8,10}};
    for(auto e:input){
        G[e[0]].push_back(e[1]);
        G[e[1]].push_back(e[0]);
    }
    dfs(0, -1);
    for(int i=0;i<=10;i++)
        for(int j=0;j<=10;j++)
            cout<<lca(i,j)<<((j==10)?'\n':' ');
    return 0;
}

## 樹鍊剖分
- 一棵樹上進行路徑的修改、求極值、求和
- 把樹拆成一條條重鍊
- [CP Heavy-light decomposition](https://cp-algorithms.com/graph/hld.html)