Tree Basics

Tree เป็น connected graph ที่ไม่มี cycle มี $n$ nodes และ $n-1$ edges

คุณสมบัติพื้นฐาน

• มี unique path ระหว่าง nodes ทุกคู่
• การลบ edge ใดๆ จะทำให้ graph ไม่ connected
• การเพิ่ม edge ใดๆ จะสร้าง cycle

การแทน Tree

1. Adjacency List

int n;
vector<vector<int>> adj;

void addEdge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

2. Parent Array (Rooted Tree)

vector<int> parent;
vector<int> depth;

void dfs(int u, int p, int d) {
    parent[u] = p;
    depth[u] = d;
    for (int v : adj[u]) {
        if (v != p) {
            dfs(v, u, d + 1);
        }
    }
}

Tree Traversal

DFS - Preorder, Inorder, Postorder

vector<int> preorder, postorder;
vector<int> tin, tout;
int timer = 0;

void dfs(int u, int p) {
    tin[u] = timer++;
    preorder.push_back(u);
    
    for (int v : adj[u]) {
        if (v != p) {
            dfs(v, u);
        }
    }
    
    tout[u] = timer++;
    postorder.push_back(u);
}

Euler Tour

Euler Tour แปลง tree เป็น array เพื่อใช้กับ data structures เช่น Segment Tree

vector<int> euler;
vector<int> first;  // first occurrence
vector<int> last;   // last occurrence

void eulerTour(int u, int p) {
    first[u] = euler.size();
    euler.push_back(u);
    
    for (int v : adj[u]) {
        if (v != p) {
            eulerTour(v, u);
            euler.push_back(u);  // return to u
        }
    }
    
    last[u] = euler.size() - 1;
}

Subtree Properties

Subtree Size

vector<int> subtreeSize;

int calcSize(int u, int p) {
    subtreeSize[u] = 1;
    for (int v : adj[u]) {
        if (v != p) {
            subtreeSize[u] += calcSize(v, u);
        }
    }
    return subtreeSize[u];
}

Subtree Sum (with values)

vector<long long> value, subtreeSum;

long long calcSum(int u, int p) {
    subtreeSum[u] = value[u];
    for (int v : adj[u]) {
        if (v != p) {
            subtreeSum[u] += calcSum(v, u);
        }
    }
    return subtreeSum[u];
}

Tree Diameter

Method 1: Two BFS

pair<int, int> bfs(int start) {
    vector<int> dist(n, -1);
    queue<int> q;
    q.push(start);
    dist[start] = 0;
    
    int farthest = start, maxDist = 0;
    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] > maxDist) {
                    maxDist = dist[v];
                    farthest = v;
                }
            }
        }
    }
    
    return {farthest, maxDist};
}

int treeDiameter() {
    auto [node1, _] = bfs(0);
    auto [node2, diameter] = bfs(node1);
    return diameter;
}

Method 2: DFS

int diameter = 0;

int dfs(int u, int p) {
    int maxDepth1 = 0, maxDepth2 = 0;
    
    for (int v : adj[u]) {
        if (v != p) {
            int d = dfs(v, u) + 1;
            if (d > maxDepth1) {
                maxDepth2 = maxDepth1;
                maxDepth1 = d;
            } else if (d > maxDepth2) {
                maxDepth2 = d;
            }
        }
    }
    
    diameter = max(diameter, maxDepth1 + maxDepth2);
    return maxDepth1;
}

Tree Center

Node(s) ที่ minimize maximum distance ไปยัง nodes อื่นทั้งหมด

vector<int> findCenter() {
    vector<int> degree(n);
    queue<int> leaves;
    
    for (int i = 0; i < n; i++) {
        degree[i] = adj[i].size();
        if (degree[i] <= 1) {
            leaves.push(i);
        }
    }
    
    int remaining = n;
    while (remaining > 2) {
        int leafCount = leaves.size();
        remaining -= leafCount;
        
        for (int i = 0; i < leafCount; i++) {
            int u = leaves.front();
            leaves.pop();
            
            for (int v : adj[u]) {
                if (--degree[v] == 1) {
                    leaves.push(v);
                }
            }
        }
    }
    
    vector<int> centers;
    while (!leaves.empty()) {
        centers.push_back(leaves.front());
        leaves.pop();
    }
    
    return centers;  // 1 or 2 centers
}

Rerooting Technique

ใช้เมื่อต้องการคำนวณค่าบางอย่างสำหรับทุก node เป็น root

ตัวอย่าง: Sum of distances จากทุก node

vector<long long> answer;
vector<int> subtreeSize;

void dfs1(int u, int p) {
    subtreeSize[u] = 1;
    for (int v : adj[u]) {
        if (v != p) {
            dfs1(v, u);
            subtreeSize[u] += subtreeSize[v];
            answer[u] += answer[v] + subtreeSize[v];
        }
    }
}

void dfs2(int u, int p) {
    for (int v : adj[u]) {
        if (v != p) {
            // Reroot from u to v
            answer[v] = answer[u] - subtreeSize[v] + (n - subtreeSize[v]);
            dfs2(v, u);
        }
    }
}

void solve() {
    dfs1(0, -1);  // Root at 0
    dfs2(0, -1);  // Reroot to all other nodes
}

Binary Lifting for Ancestors

หา ancestor ที่ $k$ ระดับขึ้นไปใน $O(\log n)$

const int LOG = 20;
vector<vector<int>> up;  // up[v][j] = ancestor 2^j levels up from v

void preprocess(int root) {
    up.assign(n, vector<int>(LOG, -1));
    
    function<void(int, int)> dfs = [&](int u, int p) {
        up[u][0] = p;
        for (int j = 1; j < LOG; j++) {
            if (up[u][j-1] != -1) {
                up[u][j] = up[up[u][j-1]][j-1];
            }
        }
        for (int v : adj[u]) {
            if (v != p) dfs(v, u);
        }
    };
    
    dfs(root, -1);
}

int getAncestor(int v, int k) {
    for (int j = 0; j < LOG && v != -1; j++) {
        if (k & (1 << j)) {
            v = up[v][j];
        }
    }
    return v;
}

Complexity Summary

Operation	Time
DFS/BFS	$O(n)$
Tree diameter	$O(n)$
Find center	$O(n)$
Binary lifting preprocess	$O(n \log n)$
Get k-th ancestor	$O(\log n)$