{%hackmd @themes/dracula %}
<style>
.markdown-body pre, .markdown-body code {
background-color: #272822 !important;
}
.CodeMirror span.cm-operator, .markdown-body pre code span{
background: none !important;
}
img {
display: block;
width: 30rem;
aspect-ratio: 1:1
}
</style>
# ***$LCA$***
## **Đề bài**
https://cses.fi/problemset/task/1688

Tóm tắt: Cho một cây gồm $n$ đỉnh có gốc tại đỉnh $1$. Có $q$ truy vấn, mỗi truy vấn gồm $1$ cặp số $(u,v)$ và ta cần tìm $LCA$ của $u$ và $v$.

Giới hạn: $N,Q≤2⋅10^{5}$
## **Giải thích**
1. *Ancestor*
- Một node $u$ là ancestor (tổ tiên) của node $v$ nếu $u$ xuất hiện trên đường đi từ node gốc của cây đến node $v$. Khi đó, node $v$ được gọi là cháu (descendant) của node $u$.
2. *$LCA$ (Lowest Common Ancestor)*
- Lowest common ancestor ($LCA$) của $u$ và $v$ là điểm cùng là tổ tiên của $u$ và $v$ và nằm xa nhất so với đỉnh gốc của cây.
- Tổ tiên thứ $k$ của $u$ là đỉnh mà chúng ta sẽ đi đến nếu chúng ta di chuyển lên cha của đỉnh $u$ $k$ lần.

## **Phương pháp giải**
### *Ngây thơ (Em yêu anh <3)*
- Đặt $h[u]$ là độ cao của đỉnh u.
- Giả sử $h[u]>h[v]$:
- Bước 1: Cho u nhảy lên cha của u đến khi $h[u]=h[v]$.
- Bước 2: Cho $u$ và $v$ nhảy lên cha của chúng đến khi $u$ và $v$ trùng nhau
- Đỉnh tìm được sẽ là $LCA$ của $u$ và $v$ ban đầu.


Độ phức tạp truy vấn: $O(n)$ (HETCUU)

Implementation (Nguồn: VNOI)

vector<int> g[N]; // g[u]: tập các đỉnh kề với u
int par[N];     // par[u] = p nếu cha của u là p
int h[N];
void dfs(int u) {
    for (int v : g[u]) {
        if (v == par[u]) continue;
        h[v] = h[u] + 1;
        par[v] = u;
        dfs(v);
    }
}

int lca(int u, int v) {
    // Không mất tính tổng quát, xét h[u] >= h[v]
    if (h[u] < h[v]) swap(u, v);

    // cho u nhảy lên cha đến khi h[u] = h[v]
    while (h[u] > h[v])
        u = par[u];

    // cho u và v nhảy lên cha đến khi u trùng v
    while (u != v) {
        u = par[u];
        v = par[v];
    }

    return u;
}

### *Euler tour + solving RMQ (Gigachad)*

#### Thuật toán Euler Tour (Euler Tour Technique)

> Khái quát về Euler tour

Euler tour (Chu trình Euler) trong đồ thị vô hướng là một chu trình đi qua mỗi cạnh của đồ thị đúng một lần và có đỉnh đầu trùng với đỉnh cuối.

Mục đích của thuật toán là để trải phẳng cây nhằm áp dụng các thao tác xử lý trên mảng 1 chiều.

> Tạo dãy Euler tour

Ta cần xây dựng 3 Mảng:
- 𝐸: dãy thứ tự thăm của các nút trên đường đi Euler, 𝐸[𝑖] là nút được thăm thứ 𝑖 trên đường đi.
- 𝐿: tầng của các nút, 𝐿[𝑖] là tầng của nút 𝐸[𝑖].
- 𝐻: 𝐻[𝑖] là vị trí xuất hiện đầu tiên của nút 𝑖 trên Euler Tour.

Chúng ta sẽ sử dụng thuật toán DFS để duyệt qua cây:
- Mỗi khi truy cập một đỉnh bất kỳ, ta thêm đỉnh đó vào đường đi.
- Trước khi rời khỏi một đỉnh (trở về cha), nếu đỉnh đó khác gốc của cây, ta thêm cha của đỉnh vào đường đi.
- Mỗi khi thêm một đỉnh vào đường đi, ta sẽ cập nhật các mảng 𝐸,𝐿,𝐻.



Implementation

void dfs(int u, int h)
{
    vis[u] = true;
    L[u] = h;
    H[u] = E.size();
    E.push_back(u);
    for (int v: p[u])
        if (!vis[v]) 
        {
            dfs(v, h + 1);
            E.push_back(u);
        }
}

#### Ứng dụng Euler tour vào LCA

> Ta có thể biến đổi bài toán LCA thành bài toán RMQ trong thời gian tuyến tính, do đó mà mọi thuật toán để giải bài toán RMQ đều có thể sử dụng để giải bài toán LCA.

Xét ví dụ

Để ý rằng 𝐿𝐶𝐴(𝑢,𝑣) là nút gần gốc nhất xuất hiện giữa lúc thăm 𝑢 và 𝑣 trong phép duyệt DFS. Vì thế ta có thể xét tất cả các phần tử giữa các cặp chỉ số bất kì của 𝑢 và v (thông thường sẽ lấy $first[u]$ và $first[v]$) trong dãy Euler Tour và tìm nút cao nhất. Bài toán lúc này sẽ trở thành bài toán Range Minimum Query (RMQ).

Vì sao $LCA(u,v)$ lại nằm trên đoạn $(first[u],first[v])$?
- Gọi $x$ là $LCA(u,v)$
- Có thể thấy rằng $u$ và $v$ phải cùng thuộc cây con của $x$
- $u$ và $v$ sẽ không cùng thuộc cây con của $y$ với $y$ là bất kì con của $x$ (vì nếu thế $LCA(u,v)= y$)
- Để đi từ cây con của $y1$ đến cây con của $y2$ (với $y1$,$y2$ đều là con của $x$) thì bắt buộc phải thông qua $x$

=> Đoạn $(first[u],first[v])$ sẽ luôn chứa $LCA(u,v)$

Vì sao $LCA(u,v)$ lại là nút cao nhất trên đoạn?
- Gọi $x$ là $LCA(u,v)$
- Có thể thấy, Đoạn đang xét $(first[u],first[v])$ không thể nào chứa $parent[x]$ (Vì đoạn $(first[u],first[v])$ nằm trong cây con của $LCA(u,v)$).
- Qua đó, $LCA(u,v)$ sẽ là nút cao nhất trên đoạn.

> Giải bài toán RMQ (Range Minimum Query)

1. *Segment tree*
Implementation (Nguồn: VNOI)

void build(int id, int tl, int tr)
{
    if (tl == tr)
    {
        t[id] = E[tl];
        return;
    }
    int tm = (tl + tr) >> 1;
    build(id*2, tl, tm);
    build(id*2+1, tm+1, tr);
    t[id] = (L[t[id*2]] < L[t[id*2+1]]) ? t[id*2] : t[id*2+1];
}

int get_min(int id, int tl, int tr, int l, int r)
{
    if (tl > r || tr < l)
        return -1;
    if (l <= tl && tr <= r)
        return t[id];
    int tm = (tl + tr) >> 1;
    int left = get_min(id*2, tl, tm, l, r),
        right = get_min(id*2+1, tm+1, tr, l, r);
    if (left == -1)
        return right;
    if (right == -1)
        return left;
    return (L[left] < L[right]) ? left : right;
}

2. *Sparse table*
Implementation (Nguồn: VNOI)

int a[N], st[LG + 1][N];
void preprocess() {
    for (int i = 1; i <= n; ++i) st[0][i] = a[i];
    for (int j = 1; j <= LG; ++j)
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
            st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
int queryMin(int l, int r) {
    int k = __lg(r - l + 1);
    return min(st[k][l], st[k][r - (1 << k) + 1]);
}

<!-- gì gì đó -->

### *Binary lifting (Classic)*
#### Đề bài
Cho một cây gồm N đỉnh có gốc tại đỉnh 1, Có $Q$ truy vấn, mỗi truy vấn gồm 1 cặp số $(u,k)$, ta cần in ra tổ tiên thứ $k$ của $u$. ($N,Q <= 1e5$)
#### Ngây thơ
>Ta lặp lại câu lệnh $u = par[u]$ trong $k$ lần với mỗi truy vấn.

Implementation (Nguồn: VNOI)

int par[N];
int ancestor_k(int u, int k) {
    while (k >= 1) {
        u = par[u];
        --k;
    }
    return u;
}

Độ phức tạp truy vấn: $O(n)$ (HETCUU)
#### Cải tiến 1
>Thay vì nhảy từng bước có độ dài là $1$, ta có thể nhảy với độ dài là $2$.

Tạo thêm mảng $up2$ để lưu tổ tiên thứ $2$ của $u$.

Implementation (Nguồn: VNOI)

int par[N], up2[N];
void preprocess() {
    for (int u = 1; u <= n; ++u)
        up2[u] = par[par[u]];
}

int ancestor_k(int u, int k) {
    while (k >= 2) {
        u = up2[u];
        k -= 2;
    }
    if (k >= 1) {
        u = par[u];
        --k;
    }
    return u;
}

Độ phức tạp truy vấn: $O(N/2)$
#### Cải tiến 1.69
> Tương tự như Cải tiến 1, nếu chúng ta nhảy với độ dài là $4$ thay vì $2$, độ phức tạp mỗi truy vấn sẽ tiếp tục giảm.

Tạo thêm mảng $up4$ để lưu tổ tiên thứ $4$ của $u$.

Implementation (Nguồn: VNOI)

int par[N], up2[N], up4[N];
void preprocess() {
    for (int u = 1; u <= n; ++u) up2[u] = par[par[u]];
    for (int u = 1; u <= n; ++u) up4[u] = up2[up2[u]];
}

int ancestor_k(int u, int k) {
    while (k >= 4) u = up4[u], k -= 4;
    if (k >= 2) u = up2[u], k -= 2;
    if (k >= 1) u = par[u], --k;
    return u;
}

Độ phức tạp mỗi truy vấn: $O(n/4)$

#### Cải tiến 2: EPIC (NON)BINARY LIFTING
> Nhận xét 1: Nếu chúng ta liên tục lặp lại cải tiến 1.5 (nhảy $8,16,32,..., 2^{x}$ ) thì độ phức tạp của mỗi truy vấn sẽ giảm còn $O(log_2{n})$

Qua đó, thay vì nhảy từng bước có độ dài $1$, chúng ta nhảy từng bước với độ dài $2^{j}$ với $j$ từ $log_{2}(maxlog)$ về $0$ với $maxlog = log_{2}n$

>Nhận xét 2: Ta luôn có thể tách một số nguyên dương thành tổng các lũy thừa phân biệt của $2$ (hệ nhị phân). Ví dụ: $25=2^{4}+2^{3}+2^{0}=11001_{2}$.

Qua đó, để nhảy lên tổ tiên thứ $k$ của $u$, ta có thể duyệt $j$ từ $0$ đến $log_{2}(k)$, nếu bit thứ $j$ của $k$ là $1$ thì ta cho $u$ nhảy lên tổ tiên thứ $2^{j}$ của nó.

Cách cài đặt:

Gọi $up[u][j]$ là tổ tiên thứ $2^{j}$ của u

Cha của u là tổ tiên thứ 1 (đầu tiên) của u ⇒ $up[u][0]=par[u]$
Giả sử $x$ là tổ tiên thứ $2^{y-1}$ của u, tổ tiên thứ $2^{j}$ của u sẽ là tổ tiên thứ $2^{j-1}$ của $x$ (vì $2^{j-1}+2^{j-1} = 2^{j}$ )

$\left\{\begin{matrix}
&x &= up[u][j-1]
\\
&up[u][j] &= up[x][j-1]
\end{matrix}\right.$

Gọi
- $H[u]$ là khoảng cách từ node $u$ đến gốc của cây
- $x$ là tổ tiên thứ $2^{j-1}$ của $u$

Ta có công thức truy hồi sau:

$\left\{\begin{matrix}
&up[u][j] & = par[u]& (j=0)
\\
&up[u][j] & = up[x][j−1] &(j>0;2^{j}≤h[u])
\\
&up[u][j] & = 0(NULL) &(j>0;2^{j}>h[u])
\end{matrix}\right.$

Sau đó, chúng ta sẽ nâng $u$ lên một khoảng cách bằng $k$ dựa vào biểu diễn nhị phân của $k$

Implementation (Nguồn: VNOI)

int par[N], up[N][17];
void preprocess() {
    for (int u = 1; u <= n; ++u) up[u][0] = par[u];
    for (int j = 1; j < 17; ++j)
        for (int u = 1; u <= n; ++u)
            up[u][j] = up[up[u][j - 1]][j - 1];
}

int ancestor_k(int u, int k) {
    for (int j = 16; j >= 0; --j)
        if (k >= (1 << j)) u = up[u][j], k -= 1 << j;
    return u;
}

Độ phức tạp truy vấn: $O(log_{2}n)$

#### Áp dụng Binary Lifting vào LCA

Bằng cách sử dụng mảng $up$, ta có thể nhảy từ $u$ đến bất kì tổ tiên nào chỉ trong $O(logN)$ (bài toán tìm tổ tiên thứ $k$). Ta có thể tính mảng này bằng cách duyệt $DFS$.

Implementation (Nguồn: VNOI)

void dfs(int u) {
    for (int v : g[u]) {
        if (v == up[u][0]) continue;
        h[v] = h[u] + 1;
        
        up[v][0] = u;
        for (int j = 1; j < 20; ++j)
            up[v][j] = up[up[v][j - 1]][j - 1];

        dfs(v);
    }
}

Cách tìm $LCA$ giống thuật toán ngây thơ ban đầu, nhưng để tăng tốc, thay vì nhảy lên cha ở mỗi bước, ta dùng mảng $up$ để nhảy.

Cụ thể:

- Gọi $h[u]$ là độ cao của đỉnh u. Để tính $LCA(u,v)$, giả sử $h[u]>h[v]$, đầu tiên ta tìm $x$ là tổ tiên của $u$ và có $h[x]=h[v]$:
- Rõ ràng, ta cần nhảy từ $u$ lên cha thứ $k=h(u)−h(v)$.
- Sau khi $u$ và $v$ đã ở cùng độ cao, ta sẽ tính $LCA(u,v)$:
- Nếu $u=v$ thì $LCA(u,v)$ chính là $u$ và $v$
- Nếu $u≠v$ thì ta dùng Binary Lifting để tìm $k$ lớn nhất sao cho tổ tiên thứ $k$ của $u$ và $v$ khác nhau (không phải tổ tiên chung). Lúc này, tổ tiên thứ $k+1$ chính là tổ tiên chung của u và v.
- Ta duyệt $j$ từ $log_{2}(h[u])$ về $0$
- Nếu tổ tiên thứ $2^{j}$ của $u$ và $v$ khác nhau thì ta cho cả $u$ và $v$ nhảy lên tổ tiên thứ $2^{j}$ của chúng.
- Cuối cùng thì $u$ và $v$ sẽ có cùng cha (tổ tiên thứ $k+1$ là cha của tổ tiên thứ $k$), khi đó $LCA(u,v)$ $=$ $par[u]$ $=$ $par[v]$ $=$ $up[u][0]$ $=$ $up[v][0]$.

Implementation (Nguồn: VNOI)

int h[N], up[N][20];
int lca(int u, int v) {
    if (h[u] != h[v]) {
        if (h[u] < h[v]) swap(u, v);
    
        // Tìm tổ tiên u' của u sao cho h(u') = h(v)
        int k = h[u] - h[v];
        for (int j = 0; (1 << j) <= k; ++j)
            if (k >> j & 1) // Nếu bit thứ j của k là 1
                u = up[u][j];
    }
    if (u == v) return u;
    
    // Tìm lca(u, v)
    int k = __lg(h[u]);
    for (int j = k; j >= 0; --j)
        if (up[u][j] != up[v][j]) // Nếu tổ tiên thứ 2^j của u và v khác nhau
            u = up[u][j], v = up[v][j];
    return up[u][0];
}

Độ phức tạp khởi tạo: $O(n*log_{2}n)$
Độ phức tạp truy vấn: $O(log_{2}n)$

### *HLD (Helpless, Lament, Despair)*

Xuất phát từ trường hợp suy biến của cây: mỗi nút của cây chỉ có đúng 1 con (trừ 1 nút lá không có con). Với một cây suy biến ta hoàn toàn có thể tìm $LCA(u,v)$ trong thời gian $O(1)$ (đỉnh nào gần gốc hơn trong 2 đỉnh $u, v$ sẽ là $LCA(u,v)$).

Tư tưởng của Heavy Light Decomposition sẽ là chia cây ban đầu ra thành nhiều cây suy biến.


Những đoạn cùng màu là một cây suy biến. Nếu coi mỗi cây suy biến là một đỉnh thì ta sẽ được một cây mới gọi là cây rút gọn. Sau đây là một cách chia cây để cây rút gọn thu được có độ cao $O(LogN)$ với N là số nút của cây ban đầu:

- Xuất phát từ đỉnh gốc
- Với mỗi đỉnh nếu là lá thì nó sẽ là kết thúc của một cây suy biến
- Nếu không ta sẽ phát triển tiếp cây suy biến này xuống đỉnh con có trọng lượng lớn nhất, các đỉnh con khác sẽ là nút gốc của những cây suy biến mới. Trọng lượng của một nút $u$ là số nút trong cây con của $u$.

Còn vì sao nó là $log(N)$ thì ¯\\\_(ツ)_/¯

Để thực hiện chất vấn $LCA(u,v)$ ta lần lượt nhảy từ $u$ và $v$ trở về gốc của cây.
- Từ một đỉnh ta thực hiện lần lượt một bước nhảy dài tới gốc của cây suy biến chứa nó và một bước nhảy ngắn tới nút cha (qua đó chuyển sang cây suy biến mới).
- Sau khi xác định được cây suy biến chứa $LCA(u,v)$, ta có thể xác định được đỉnh $u1$, $v1$ tương ứng là nút đầu tiên ta gặp khi nhảy từ $u, v$ tới cây suy biến chứa $LCA(u,v)$.
- Sau đó chỉ cần so sánh xem $u1$ hay $v1$ gần gốc hơn là có thể xác định được $LCA(u,v)$.

Implementation (nguồn VNOI wiki)

void Dfs(int s, int p = -1) {
    Sz[s] = 1;
    for(int u: AdjList[s]) {
        if(u == p) continue;
        Par[u] = s;
        Depth[u] = Depth[s] + 1;
        Dfs(u, s);
        Sz[s] += Sz[u];
    }
}

void Hld(int s, int p = -1) {
    if(!ChainHead[CurChain]) {
        ChainHead[CurChain] = s;
    }
    ChainID[s] = CurChain;
    Pos[s] = CurPos;
    Arr[CurPos] = s;
    CurPos++;
    int nxt = 0;
    for(int u: AdjList[s]) {
        if(u != p) {
            if(nxt == 0 || Sz[u] > Sz[nxt]) nxt = u;
        }
    }
    if(nxt) Hld(nxt, s);
    for(int u: AdjList[s]) {
        if(u != p && u != nxt) {
            CurChain++;
            Hld(u, s);
        }
    }
}

int LCA(int u, int v) {
    while(ChainID[u] != ChainID[v]) {
        if(ChainID[u] > ChainID[v]) {
            u = Par[ChainHead[ChainID[u]]];
        }
        else {
            v = Par[ChainHead[ChainID[v]]];
        }
    }
    if(Depth[u] < Depth[v]) return u;
    return v;
}

### *Xử lý Offline (I sleep zzz)*
<!-- ### Solving RMQ by LCA -->
(Nguồn: VNOI wiki)

Đây là một phương pháp để giải bài toán LCA khi đã biết trước mọi câu hỏi chất vấn. Cách làm này tuy không linh hoạt nhưng thời gian chạy khá nhanh và tiết kiệm bộ nhớ. Tư tưởng của phương pháp này là trả lời các câu chất vấn theo một thứ tự khác dễ dàng hơn. Với mỗi nút của cây ta sẽ lưu nó trong một tập hợp có nhãn. Ban đầu mỗi nút thuộc một tập hợp khác nhau và nhãn của tập hợp chính là chỉ số của nút đó. Sau đó ta thực hiện thủ tục DFS, trước khi thoát ra khỏi thủ tục DFS ta thực hiện 2 thao tác sau :

- Tìm cha chung của 𝑢 với các đỉnh 𝑣 mà thủ tục DFS(v) đã được thực thi. Đỉnh cha chung chính là nhãn của tập hợp chứa 𝑣.
- Hợp nhất tập hợp chứa 𝑢 với tập hợp chứa par(𝑢) và lấy nhãn là par(𝑢).

Ta sẽ chứng minh “Đỉnh cha chung chính là nhãn của tập hợp chứa v”. Giả sử 𝑖=𝐿𝐶𝐴(𝑢,𝑣). Sau khi thực thi thủ tục DFS(v) xong, từ 𝑣 thủ tục DFS phải đi về 𝑖 và rẽ xuống 𝑢 để có thể thực hiện DFS(u). Trong quá trình đi về 𝑖, nó sẽ hợp nhất 𝑣 với cha 𝑣, ông 𝑣,.. rồi với 𝑖. Do đó nhãn của tập chứa 𝑣 chính là 𝑖.

Để thực hiện thao tác hợp nhất 2 tập hợp với thời gian ngắn, ta có thể sử dụng cấu trúc disjoint set giống như trong thuật toán Kruskal. Độ phức tạp của phương pháp này là (𝑀+𝑁)𝑙𝑜𝑔(𝑁) với 𝑀 là số thao tác.

Implementation (nguồn cp-algorithms)

vector<vector<int>> adj;
vector<vector<int>> queries;
vector<int> ancestor;
vector<bool> visited;

void dfs(int v)
{
    visited[v] = true;
    ancestor[v] = v;
    for (int u : adj[v]) {
        if (!visited[u]) {
            dfs(u);
            union_sets(v, u);
            ancestor[find_set(v)] = v;
        }
    }
    for (int other_node : queries[v]) {
        if (visited[other_node])
            cout << "LCA of " << v << " and " << other_node
                 << " is " << ancestor[find_set(other_node)] << ".\n";
    }
}

void compute_LCAs() {
    // initialize n, adj and DSU
    // for (each query (u, v)) {
    //    queries[u].push_back(v);
    //    queries[v].push_back(u);
    // }

    ancestor.resize(n);
    visited.assign(n, false);
    dfs(0);
}

## **Bài Tập**

#### Độ khó: Easy :hearts:

>Company Queries: https://cses.fi/problemset/task/1688

<!-- >Code tham khảo (Nguồn: Nguyễn Lý Thành Tài)
<details>
<summary>
Solution (Spoiler alert)
</summary>

*Skill Issue <333*

#include <bits/stdc++.h>
#define anhminhhuycute "data."
using namespace std;
const int N = (int) 4e5+10;
int t[4*N];
vector<int> E;
int L[N], H[N];
bool vis[N];
vector<int> p[N];
void build(int id, int tl, int tr)
{
    if (tl == tr)
    {
        t[id] = E[tl];
        return;
    }
    int tm = (tl + tr) >> 1;
    build(id*2, tl, tm);
    build(id*2+1, tm+1, tr);
    t[id] = (L[t[id*2]] < L[t[id*2+1]]) ? t[id*2] : t[id*2+1];
}
int get_min(int id, int tl, int tr, int l, int r)
{
    if (tl > r || tr < l)
        return -1;
    if (l <= tl && tr <= r)
        return t[id];
    int tm = (tl + tr) >> 1;
    int left = get_min(id*2, tl, tm, l, r),
        right = get_min(id*2+1, tm+1, tr, l, r);
    if (left == -1)
        return right;
    if (right == -1)
        return left;
    return (L[left] < L[right]) ? left : right;
}
int lca(int u, int v) 
{
    int left = H[u], right = H[v];
    if (left > right)
        swap(left, right);
    return get_min(1, 0, E.size()-1, left, right);
}
void dfs(int u, int h)
{
    vis[u] = true;
    L[u] = h;
    H[u] = E.size();
    E.push_back(u);
    for (int v: p[u]) {
        if (!vis[v]) {
            dfs(v, h + 1);
            E.push_back(u);
        }
    }
}
int main()
{
    // freopen(anhminhhuycute"inp", "r", stdin);
    cin.tie(0) -> sync_with_stdio(0);
    int n, q;
    cin >> n >> q;
    for (int i = 2; i <= n; i++)
    {
        int x;
        cin >> x;
        p[x].push_back(i);
    }
    dfs(1, 0);
    build(1,0,E.size()-1);
    while (q--)
    {
        int a, b; 
        cin >> a >> b;
        cout << lca(a, b) << '\n';
    }
    return 0;
}

</details>
-->
#### Độ khó: Normal :thumbsup:
> Distance Queries: https://cses.fi/problemset/task/1135
<!-- >Code tham khảo (Nguồn: Nguyễn Lý Thành Tài) -->
<details>
<summary>
Solution (Spoiler alert)
</summary>

Với mỗi truy vấn, tìm $LCA(u,v)$ và đáp án sẽ là $L[u] + L[v] - 2*L[LCA(u,v)]$.

Độ phức tạp: $O(N*log_{2}N)$
<!--

#include <bits/stdc++.h>
#define anhminhhuycute "data."
using namespace std;
const int N = (int) 4e5+10;
int t[4*N];
vector<int> E;
int L[N], H[N];
bool vis[N];
vector<int> p[N];
void build(int id, int tl, int tr)
{
    if (tl == tr)
    {
        t[id] = E[tl];
        return;
    }
    int tm = (tl + tr) >> 1;
    build(id*2, tl, tm);
    build(id*2+1, tm+1, tr);
    t[id] = (L[t[id*2]] < L[t[id*2+1]]) ? t[id*2] : t[id*2+1];
}
int get_min(int id, int tl, int tr, int l, int r)
{
    if (tl > r || tr < l)
        return -1;
    if (l <= tl && tr <= r)
        return t[id];
    int tm = (tl + tr) >> 1;
    int left = get_min(id*2, tl, tm, l, r),
        right = get_min(id*2+1, tm+1, tr, l, r);
    if (left == -1)
        return right;
    if (right == -1)
        return left;
    return (L[left] < L[right]) ? left : right;
}
int lca(int u, int v) 
{
    int left = H[u], right = H[v];
    if (left > right)
        swap(left, right);
    return get_min(1, 0, E.size()-1, left, right);
}
void dfs(int u, int h)
{
    vis[u] = true;
    L[u] = h;
    H[u] = E.size();
    E.push_back(u);
    for (int v: p[u]) {
        if (!vis[v]) {
            dfs(v, h + 1);
            E.push_back(u);
        }
    }
}
int dist(int a, int b)
{
    return L[a] + L[b] - 2*L[lca(a,b)];
}
int main()
{
    // freopen(anhminhhuycute"inp", "r", stdin);
    cin.tie(0) -> sync_with_stdio(0);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        p[u].push_back(v);
        p[v].push_back(u);
    }
    dfs(1, 0);
    build(1,0,E.size()-1);
    while (q--)
    {
        int a, b; 
        cin >> a >> b;
        cout << dist(a, b) << '\n';
    }
    return 0;
}

</details>

> Sloth Naptime: https://codeforces.com/gym/102694/problem/C
<!-- Code tham khảo (Nguồn: KawakiMeido) -->
<details>
<summary>
Solution (Spoiler alert)
</summary>

Có thể thấy rằng để tiết kiệm năng lượng nhất thì con lười sẽ đi từ điểm $a$ lên $LCA(a,b)$ và xuống $b$.

Gọi $dist(i,j)$ là khoảng cách từ node $i$ đến node $j$ trên cây
$Dist1 = dist(a,lca(a,b))$
$Dist2 = dist(b,lca(a,b))$

Như vậy, bài toán sẽ chia ra 3 trường hợp:
- $c ≥ Dist1 + Dist2$ - lười sẽ dừng tại điểm $b$
- $Dist1 + Dist2 > c ≥ Dist1$ - lười sẽ dừng tại tổ tiên thứ $(Dist2-(c-Dist1))$ của $b$
- $Dist1 > c$ - lười sẽ dừng tại tổ tiên thứ $c$ của $a$

Như vậy, chúng ta chỉ cần xây dựng thuật toán tìm $LCA$ và thuật toán Binary Lifting tìm tổ tiên thứ $k$ của 1 node trên cây.

Độ phức tạp: $O(N*log_{2}N)$
<!--

#include <bits/stdc++.h>
#define endl "\n"
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second

using namespace std;

const int maxn = 3e5+10;
const int INF = 2e9;

int test;
int n,q;
int h[maxn];
vector<int> a[maxn];
int up[maxn][21];

void dfs(int u, int p){
    h[u] = h[p]+1;
    up[u][0] = p;

    for (int i=1; i<=__lg(h[u]); i++){
        int v = up[u][i-1];
        up[u][i] = up[v][i-1];
    }

    for (auto v:a[u]){
        if (v == p) continue;
        dfs(v,u);
    }
}

int Lift(int u, int k){
    for (int lg=0; lg<=__lg(k); lg++){
        if ((k & (1<<lg))) u = up[u][lg];
    }
    return u;
}

int FindLCA(int u, int v){
    if (h[u]!=h[v]){
        if (h[u] > h[v]) swap(u,v);

        int k = h[v] - h[u];

        v = Lift(v,k);

    }
    if (u == v) return u;
    for (int lg = __lg(h[u]); lg>=0; lg--){
        if (up[u][lg] != up[v][lg]){
            u = up[u][lg], v = up[v][lg];
        }
    }
    return up[u][0];
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i=1; i<n; i++){
        int x,y;
        cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    dfs(1,0);
    cin >> q;
    while (q--){
        int x,y,z;
        cin >> x >> y >> z;
        int lca = FindLCA(x,y);
        int dist1 = h[x] - h[lca];
        int dist2 = h[y] - h[lca];
        if (z >= dist1+dist2) cout << y << endl;
        else if (z > dist1) cout << Lift(y,dist2 - (z - dist1)) << endl;
        else cout << Lift(x,z) << endl;
    }

    return 0;
}

-->
</details>

#### Độ khó: Hard :anger:
> Omsk Metro (Hard version): https://codeforces.com/contest/1843/problem/F2
Code tham khảo (Nguồn: KawakiMeido)
<details>
<summary>
Solution (Spoiler alert)
</summary>

Giả sử ta cần xử lý truy vấn trên đoạn $(u,v)$, gọi $mn$ là giá trị nhỏ nhất của đoạn con trên $(u,v)$, $mx$ là giá trị lớn nhất của đoạn con trên $(u,v)$. Tập giá trị của đoạn con trên $(u,v)$ sẽ là $[mn,mx]$

Chứng minh: Giá trị của một node chỉ có thể là $1$ hoặc $-1$. Vì thế nếu chúng ta xét lấy thêm một node liền trái hoặc liền phải của một đoạn con đang xét, thì giá trị chỉ có thể tăng giảm tối đa $1$ đơn vị. Qua đó, nếu một đoạn con có giá trị nguyên dương $x$ tồn tại trên đoạn, thì đoạn con có giá trị $x-1$ phải tồn tại (và ngược lại với giá trị nguyên âm). Vì thế, tập giá trị của các đoạn con trên đoạn $(u,v)$ bất kì sẽ là $[mn,mx]$.

Qua đó, bài toán sẽ trờ thành tìm mn và mx trên đường đi $(u,v)$. Để tính $mn$, chúng ta sẽ sử dụng kỹ thuật Binary Lifting. Với mỗi lần nâng, chúng ta sẽ minimum/maximum sum của prefix và suffix của đoạn vừa nâng. Giả sử ta có 2 đoạn $(u,v)$ và $(v,w)$ $(depth[u] > depth[v] > depth[w])$, $minpre(u,w)$ sẽ được tính bằng công thức $min(minpre(v,w),minpre(u,v) + sum(v,w))$. Những mảng còn lại được tính tương tự. $mn(u,w)$ sẽ được tính bằng công thức $min(mn(u,v),mn(v,w),minpre(u,v)+minsuf(v,w))$ ($mx$ cũng tương tự).

Việc còn lại cần làm là duyệt đoạn $(u,LCA(u,v))$ và $(v,LCA(u,v))$, tính các giá trị nêu trên và ghép lại để ra đáp án cuối cùng.

Độ phức tạp: $O(N*log_{2}N)$

<!--

#include <bits/stdc++.h>
#define endl "\n"
#define ll long long
#define pii pair<int,int>
#define piii pair<pii,int>
#define piiii pair<pii,pii>
#define fi first
#define se second
 
using namespace std;
 
const int maxn = 2e5+10;
const int INF = 2e9;
const int maxlog = 19;
 
int test;
int n;
int timedfs = 0;
vector<int> a[maxn];
int val[maxn];
vector<piii> query;
int tin[maxn],tout[maxn];
int up[maxn][maxlog];
int pre[maxn][maxlog][2],suf[maxn][maxlog][2],sum[maxn][maxlog];
int ans[maxn][maxlog][2];
 
void dfs(int u, int p){
    tin[u] = ++timedfs;
    up[u][0] = p;
    sum[u][0] = val[u];
    pre[u][0][0] = min(val[u],0);
    pre[u][0][1] = max(val[u],0);
    suf[u][0][0] = min(val[u],0);
    suf[u][0][1] = max(val[u],0);
    ans[u][0][0] = min(val[u],0);
    ans[u][0][1] = max(val[u],0);
    for (int lg=1; lg<maxlog; lg++){
        int v = up[u][lg-1];
        up[u][lg] = up[v][lg-1];
        sum[u][lg] = sum[u][lg-1]+sum[v][lg-1];
        pre[u][lg][0] = min(pre[u][lg-1][0],sum[u][lg-1]+pre[v][lg-1][0]);
        pre[u][lg][1] = max(pre[u][lg-1][1],sum[u][lg-1]+pre[v][lg-1][1]);
        suf[u][lg][0] = min(suf[u][lg-1][0]+sum[v][lg-1],suf[v][lg-1][0]);
        suf[u][lg][1] = max(suf[u][lg-1][1]+sum[v][lg-1],suf[v][lg-1][1]);
        ans[u][lg][0] = min({ans[u][lg-1][0],ans[v][lg-1][0],suf[u][lg-1][0] + pre[v][lg-1][0]});
        ans[u][lg][1] = max({ans[u][lg-1][1],ans[v][lg-1][1],suf[u][lg-1][1] + pre[v][lg-1][1]});
    }
 
    for (auto v:a[u]){
        dfs(v,u);
    }
    tout[u] = ++timedfs;
}
 
bool IsAnc(int u, int v){
    return (tin[u] <= tin[v] && tout[u] >= tout[v]);
}
 
int FindLCA(int u, int v){
    if (IsAnc(u,v)) return u;
    if (IsAnc(v,u)) return v;
 
    int x = v;
    for (int lg = maxlog-1; lg>=0; lg--){
        int y = up[x][lg];
        if (!IsAnc(y,u)){
            x = y;
        }
    }
    return up[x][0];
}
 
piiii BinaryJump(int u, int p){
    p = up[p][0];
    int x = 0,y = 0, t = 0,resx = 0, resy = 0;
    for (int lg = maxlog-1; lg>=0; lg--){
        int v = up[u][lg];
        if (!IsAnc(v,p)){
            t+=sum[u][lg];
            resx = min({resx,ans[u][lg][0],x + pre[u][lg][0]});
            resy = max({resy,ans[u][lg][1],y + pre[u][lg][1]});
            x = min(suf[u][lg][0], sum[u][lg] + x);
            y = max(suf[u][lg][1], sum[u][lg] + y);
            u = v;
        }
    }
    return {{resx,resy},{x,y}};
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int cnt = 0;
    cin >> test;
    while (test--){
        for (int i=1; i<=n; i++){
            a[i].clear();
        }
        tin[0] = 0;
        tout[0] = INF;
        query.clear();
        timedfs = 0;
        n = 1;
        val[1] = 1;
        int q;
        cin >> q;
        while (q--){
            char c;
            cin >> c;
            if (c == '+'){
                ++n;
                int x,v;
                cin >> x >> v;
                a[x].push_back(n);
                val[n] = v;
            }
            else{
                int u,v,x;
                cin >> u >> v >> x;
                query.push_back({{u,v},x});
            }
        }
        dfs(1,0);
        for (auto in:query){
            int u = in.fi.fi;
            int v = in.fi.se;
            int x = in.se;
            int p = FindLCA(u,v);
            piiii info1 = BinaryJump(u,p);
            piiii info2 = BinaryJump(v,p);
 
            int l = min({info1.fi.fi,info2.fi.fi,info1.se.fi + info2.se.fi + val[p]});
            int r = max({info1.fi.se,info2.fi.se,info1.se.se + info2.se.se + val[p]});
            ++cnt;
            if (l<=x && x<=r) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
    }
 
    return 0;
}

-->
</details>

#### Độ khó: Insane :fire: (Không dành cho người yếu tim)
> Double Tree: https://codeforces.com/contest/1140/problem/G (Tôi không giải được :cry:)
> 

#### ***Chúc mọi người đấm LCA thành công :muscle:***

##### *PS: Đấm code quá 180p 1 ngày có hại cho mắt nên là <3333*







<!--  -->