Cây

Cây là đồ thị liên thông không có chu trình với $N$ đỉnh và $N-1$ cạnh.

Khái niệm cơ bản

Cây có gốc (rooted tree) là cây trong đó một đỉnh được chọn làm gốc.

• Cha (parent): đỉnh liền kề gần gốc hơn
• Con (children): các đỉnh liền kề xa gốc hơn
• Lá (leaf): đỉnh không có con
• Độ sâu (depth): khoảng cách từ gốc, $\text{depth}[\text{root}]=0$
• Chiều cao (height): độ sâu lớn nhất trong cây
• Cây con của $u$ (subtree): gồm $u$ và toàn bộ hậu duệ của $u$

Duyệt cây (DFS)

const int MAXN = 2e5 + 5;
vector<int> adj[MAXN];
int par[MAXN], dep[MAXN];

void dfs(int u, int p) {
    par[u] = p;
    for (int v : adj[u])
        if (v != p) {
            dep[v] = dep[u] + 1;
            dfs(v, u);
        }
}
// dep[root] = 0; dfs(root, -1);

DFS in/out time (Euler Tour)

Gán thời điểm vào tin[u] và ra tout[u] khi DFS thì cây con của $u$ trở thành đoạn liên tục [tin[u], tout[u]] trên mảng, nên truy vấn/cập nhật cây con quy về truy vấn đoạn với Fenwick hoặc Segment Tree. Chi tiết (kiểm tra tổ tiên, truy vấn đường đi gốc-đỉnh, các dạng Euler tour, DFS không đệ quy): xem trang Euler tour trên cây.

Đường kính cây

Đường đi dài nhất giữa hai đỉnh bất kỳ. Tìm bằng hai lần BFS:

1. BFS từ đỉnh bất kỳ → tìm đỉnh xa nhất $u$
2. BFS từ $u$ → tìm đỉnh xa nhất $v$
3. Đường kính = $\text{dist}(u,v)$

pair<int,int> farthest(int src, int n) {
    vector<int> dist(n+1, -1);
    queue<int> q;
    q.push(src); dist[src] = 0;
    int far = src;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u])
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
                if (dist[v] > dist[far]) far = v;
            }
    }
    return {far, dist[far]};
}

auto [u, d1]       = farthest(1, n);
auto [v, diameter] = farthest(u, n);

Tổ tiên chung thấp nhất (LCA)

$\text{LCA}(u,v)$ là tổ tiên chung sâu nhất của $u$ và $v$; khoảng cách hai đỉnh là $\text{dep}[u]+\text{dep}[v]-2\text{dep}[\text{LCA}(u,v)]$. Các cách tính (binary lifting, Euler tour + sparse table cho truy vấn $O(1)$, Tarjan offline) và ứng dụng (tổng trên đường đi, hiệu trên cây): xem trang Tổ tiên chung thấp nhất (LCA). Cài đặt binary lifting chi tiết: Binary Lifting.

Các trang chi tiết: lộ trình học

Nhóm Cây gồm 18 trang con. Gợi ý thứ tự học từ nền tảng đến nâng cao:

1. Cấu trúc nền tảng (học trước tiên)

2. BST cân bằng / nâng cao

3. Kỹ thuật truy vấn trên cây

4. Segment Tree nâng cao

5. Cây động