Editorial for arbore: Thắc mắc của Mitrut

Hiểu bài toán

Cho một cây có N đỉnh và gốc là nút 1. Đếm số cách gán N số tự nhiên khác nhau từ 1 đến N vào các nút sao cho với mọi nút A, giá trị tại A nhỏ hơn giá trị tại tất cả các con của A (điều kiện tính chất heap). Kết quả cần in ra số dư khi chia cho 666013.

Ví dụ: Cây 5 nút. Các cách gán hợp lệ là 8 cách.

Đề bài yêu cầu đếm số cách sắp xếp các số 1..N vào cây sao cho tính chất heap của cây được giữ nguyên.

Các cách tiếp cận

Cách Quy hoạch động kết hợp Bổn phận (DP với Phân số)

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

const int MOD = 666013;
const int MAXN = 100005;

long long fact[MAXN];
long long invFact[MAXN];
int N;
vector<int> adj[MAXN];
int sz[MAXN];
long long dp[MAXN];

// Hàm tính số mũ nhanh
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// Hàm tính giai thừa và giai thừa nghịch đảo
void computeFactorial() {
    fact[0] = 1;
    invFact[0] = 1;
    for(int i = 1; i <= N; i++) {
        fact[i] = (fact[i-1] * i) % MOD;
        invFact[i] = power(fact[i], MOD - 2);
    }
}

void dfs(int u, int parent) {
    sz[u] = 1;
    dp[u] = 1;
    vector<int> childSizes;

    for(int v : adj[u]) {
        if(v == parent) continue;
        dfs(v, u);
        sz[u] += sz[v];
        dp[u] = (dp[u] * dp[v]) % MOD;
        childSizes.push_back(sz[v]);
    }

    if(!childSizes.empty()) {
        long long sum = sz[u] - 1; // Tổng kích thước các con
        // Công thức: (sum)! / (sz[child1]! * sz[child2]! * ...)
        // Logic: Chọn vị trí cho các node con trong tổng số nút con
        long long ways = fact[sum];

        for (int s : childSizes) {
            ways = (ways * invFact[s]) % MOD;
        }

        dp[u] = (dp[u] * ways) % MOD;
    }
}

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

    if (!(cin >> N)) return 0;

    for (int i = 0; i < N - 1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    computeFactorial();
    dfs(1, -1);

    cout << dp[1] << endl;

    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Đây là cách tiếp cận chính xác và hiệu quả nhất.

1. Tư duy:

   • Gọi $f(u)$ là số cách gán số cho cây con rooted tại $u$.
   • Nếu $u$ là lá, $f(u) = 1$.
   • Nếu $u$ có các con $c1, c2, ..., ck$ với kích thước tương ứng $sz(c1), ..., sz(c_k)$.
   • Để thỏa mãn điều kiện, số tại $u$ phải là số lớn nhất trong các nút thuộc cây con $u$ (giả sử các số là 1..$sz(u)$). Do đó, số tại $u$ được cố định là $sz(u)$.
   • $sz(u) - 1$ số còn lại cần được chia vào các cây con $c_i$.
   • Chúng ta cần chia $sz(c1)$ số vào cây con 1, $sz(c2)$ số vào cây con 2,...
   • Số cách chọn tập hợp số cho các con là: $?inom{sz(u)-1}{sz(c1), sz(c2), ..., sz(ck)} = \frac{(sz(u)-1)!}{\prod sz(ci)!}$.
   • Sau khi chọn được tập hợp số cho mỗi con, cách sắp xếp bên trong mỗi con là $f(c_i)$.
   • Công thức truy hồi: $f(u) = \left( \frac{(sz(u)-1)!}{\prod sz(ci)!} \right) \times \prod f(ci)$.

2. Triển khai:

   • Duyệt DFS để tính kích thước cây con $sz[u]$ và kết quả $dp[u]$.
   • Tính trước giai thừa và giai thừa nghịch lại modulo 666013 để tính tổ hợp nhanh.
   • Độ phức tạp: $O(N)$.

Cách Công thức tổng quát (Bổn phận)

// Tương tự Approach 1, nhưng có thể được nhìn nhận theo cách khác
// Số cách = N! / (Kích thước các cây con ở mỗi bước)
// Tuy nhiên, DP là cách trực tiếp nhất để hiện thực.
// Code xem ở Approach 1.

• Time Complexity: O(N log N) hoặc O(N) tùy cách tính số mũ
• Space Complexity: O(N)

Cách tiếp cận này về cơ bản là DP như trên. Có thể suy luận trực tiếp: Nếu ta viết các số từ 1 đến N vào cây theo thứ tự tăng dần (1 vào nút đầu tiên, 2 vào nút tiếp theo...), điều kiện "cha nhỏ hơn con" tương đương với việc khi thêm một nút vào cây, nút đó phải là lá. Cụ thể hơn, xét công thức: Số cách = $N! \times \prod_{u=1}^{N} \frac{1}{sz(u)}$. Đây là một công thức khác, nhưng trong bối cảnh thi đấu, việc cài đặt DP trực tiếp dựa trên suy luận chia tập hợp số là ổn định và dễ kiểm tra lỗi nhất.

Cách Brute Force (Thử tất cả các cách)

// Pseudocode
// Sinh các hoán vị của 1..N
// Với mỗi hoán vị, gán vào nút theo thứ tự BFS/DFS
// Kiểm tra điều kiện heap
// Độ phức tạp O(N! * N), chỉ chạy được N <= 7.

• Time Complexity: O(N!)
• Space Complexity: O(N)

Với N rất nhỏ (≤ 7), ta có thể sinh tất cả các cách gán số (hoán vị của 1..N) vào các nút (theo một thứ tự cố định, ví dụ duyệt cây theo BFS hoặc DFS), rồi kiểm tra xem có thỏa mãn điều kiện cha nhỏ hơn con hay không.

• Sinh hoán vị.
• Gán giá trị vào nút.
• Duyệt cây kiểm tra điều kiện.

Cách này không khả thi với N lớn.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Vấn đề có thể chia nhỏ: Số cách gán cho cây con phụ thuộc vào kích thước và cách gán của các cây con của nó.
• Tính chất Heap: Nếu số tại nút cha phải nhỏ hơn con, và ta dùng các số 1..N, thì nút cha phải chứa số lớn nhất trong tập con các nút thuộc cây con của nó (trong ngữ cảnh quy hoạch động).
• Công thức Combinatorics: Việc chia một tập hợp $S$ gồm $M$ số vào $k$ cây con có kích thước $s1, s2, ..., sk$ có $\frac{M!}{s1! s2! ... sk!}$ cách.

Lỗi thường gặp

• Sai công thức tính toán số cách chia số vào các con: Cần distinguishes giữa việc chọn số và sắp xếp số.
• Lỗi tính toán số mũ (Power) khi tính giai thừa nghịch đảo, đặc biệt với số mũ âm hoặc modulo.
• Quên modulo các phép nhân khi kết quả có thể tràn số.
• Xử lý sai khi nút không có con (base case).