Số vòng lặp tối thiểu để truyền thông tin đến tất cả nút trong cây trong C++

Cho cây có gốc (root) và các nút con. Mỗi bước, một nút có thể truyền tin cho 1 con. Gốc có thể truyền cho nhiều con song song (mỗi bước 1 con). Tìm số bước tối thiểu để tin đến tất cả nút.

Ví dụ

Cây 1: Gốc 0 có con 1,3,4,6,2. Nút 1 có con 7,2,3. Nút 4 có con 6,7. Tổng 11 nút.

Kết quả: 5 bước (mô phỏng: gốc gửi cho con nhiều con nhất trước).

Cây 2: Gốc 0 → con 1. Kết quả: 1 bước.

Phương pháp: DFS + Sắp xếp con theo độ sâu giảm dần

• DFS từ lá lên: dp[u] = số bước tối thiểu từ u đến toàn bộ cây con.
• Thu thập dp[v] của các con v, sắp xếp giảm dần.
• dp[u] = max(dp[v_i] + i + 1) với i là thứ tự gửi (0-based). Gửi cho con "khó" nhất trước.
• Kết quả = dp[root].

Ví dụ mã C++

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

class Tree {
    int n;
    vector<vector> adj;
    void dfs(int u, vector &dp) {
        dp[u] = adj[u].size();
        vector childDp;
        for (int v: adj[u]) {
            dfs(v, dp);
            childDp.push_back(dp[v]);
        }
        sort(childDp.rbegin(), childDp.rend());
        for (int i=0; i dp(n);
        dfs(0, dp);
        return dp[0];
    }
};

int main() {
    Tree T1(8);
    T1.addEdge(0,1); T1.addEdge(0,3); T1.addEdge(0,4); T1.addEdge(0,6); T1.addEdge(0,2);
    T1.addEdge(1,7); T1.addEdge(1,2); T1.addEdge(1,3);
    T1.addEdge(4,6); T1.addEdge(4,7);
    cout << "Min iterations: " << T1.minIterations() << endl;
    Tree T2(2);
    T2.addEdge(0,1);
    cout << "Min iterations: " << T2.minIterations() << endl;
    return 0;
}

Đầu ra chương trình

Minimum no. of iterations to pass information to all nodes in the tree are: 5
Minimum no. of iterations to pass information to all nodes in the tree are: 1