Hướng dẫn giải của Atcoder Educational DP Contest V - Subtree


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: minhcool

Notes

Note 1: Trong lời giải này, ~1~ là gốc

Note 2: Cây con của ~i~ là tập hợp các đỉnh ~v~ sao cho ~i~ nằm trên đường đi từ 1 tới ~v~ (hay ~i~ là tổ tiên của ~v~) trong đó có ~i~, và các cạnh nối giữa chúng

Chẳng hạn, xét cây sau đây

Các đỉnh ~3, 5, 6, 7, 8~ sẽ thuộc cây con của ~3~, vì đường đi từ ~1~ đến ~3, 5, 6, 7, 8~ đều đi qua ~3~:

  • ~1 \to 3~
  • ~1 \to 3 \to 5~
  • ~1 \to 3 \to 7~
  • ~1 \to 3 \to 6~
  • ~1 \to 3 \to 6 \to 8~

Các đỉnh 4, 9, 10 sẽ thuộc cây con của ~4~, vì đường đi từ ~1~ đến ~4, 9, 10~ đều đi qua ~4~:

  • ~1 \to 4~
  • ~1 \to 4 \to 9~
  • ~1 \to 4 \to 10~

Tất cả các đỉnh từ ~1 \to 10~ đều sẽ thuộc cây con của ~1~.

Note 3: ~C[u]~ là tập hợp các con của đỉnh ~u~

Bài toán con

Đầu tiên, chúng ta xét bài toán sau: Biết rằng đỉnh ~1~ được tô màu đen, hỏi có bao nhiêu cách để tô ~(N - 1)~ đỉnh còn lại sao cho các đỉnh trên đường đi giữa hai đỉnh được tô đen bất kì cũng được tô đen.

Chúng ta đặt ~F[i]~: Có bao nhiêu cách để tô cây con của ~i~ để thỏa mãn 1 trong 2 điều kiện:

  • Đồ thị được tô màu sao cho với hai đỉnh được tô đen bất kì, tất cả các đỉnh trên đường đi giữa hai đỉnh đó cũng được tô đen, và đỉnh ~i~ được tô màu đen
  • Không có đỉnh nào được tô màu đen

Xét đỉnh ~u~. Có hai cách để tô cây con của ~u~ thỏa mãn:

  • Tô cả cây con của ~u~ bằng màu trắng, khi đó có ~1~ cách
  • Tô đỉnh ~u~ màu đen. Khi đó, với mỗi cây con của đỉnh ~v~ (~v~ là con của ~u~), ta có hai lựa chọn
    • Không chọn đỉnh nào
    • Chọn tập hợp đỉnh liên thông với nhau và liên thông với ~u~. Vì cả cây con chỉ có ~v~ là kết nối với ~u~, do đó ~v~ cũng phải được tô màu đen. Ta nhận thấy đây chính là định nghĩa của hàm ~dp~, hay nói cách khác, với mỗi đỉnh ~v~, có ~F[v]~ cách tô màu

Ta lại nhận thấy: Với 2 con ~v, w~ bất kì của ~u~, cây con của ~v~ và ~w~ độc lập với nhau

Do đó ta có công thức:

~F[u]~ = ~1~ + ~\prod_{~v \in C[u]~}F[v]~

Bài toán chính

Chúng ta quay trở lại vởi bài toán chính.

Chúng ta có hàm ~G[i]~ khá giống với ~F[i]~, nhưng

  • Ta xét cây khi bỏ cây con của ~i~ ra
  • Cha của ~i~ được tô đen, hoặc không đỉnh nào được tô cả

Đáp án cho đỉnh i sẽ là ~(F[i] - 1) \times G[i]~

Vậy làm thế nào để tính ~G[i]~ một cách hiệu quả?

Ta sẽ có công thức sau: (~p~ là cha của ~u~) ~G[u] = 1 + G[p] \times \prod_{\substack{w \in C[p] \\ w \ne u}} F[w]~

Với mỗi ~u~, ta sẽ tính ~G~ cho các con của ~u~

Có một vấn đề: Ta cần phải tính ~\prod_{\substack{w \in C[p] \\ w \ne u}} F[w]~ nhanh, mà ta không thể lấy tích chung chia cho ~F[u]~ vì ~M~ không phải số nguyên tố.

Thay vì làm như vậy, ta sẽ lưu tích tiền tố và hậu tố (prefix and suffix product) của các con của ~u~.

Gọi ~v_{1}, v_{2}, ..., v_{x}~ là các con của ~u~.

Ta sẽ lưu

~pref[i]~ - ~\prod_{1 \le j \le i}F[v_{j}]~

~suff[i]~ - ~\prod_{i \le j \le x}F[v_{j}]~

~pref[0] = suff[x + 1] = 1~

Khi đó với mỗi đỉnh ~v_{i}~, ~\prod_{\substack{w \in C[p] \\ w \ne u}} F[w]~ = ~pref[i - 1] \times suff[i + 1]~

Độ phức tạp : ~O(N)~

Code:

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

#define pb push_back

const int N = 1e5 + 5;

const long long oo = 1e18 + 7, mod = 1e9 + 7;

long long n, M;

vector<long long> Adj[N];

long long f[N], g[N];

long long pref[N], suff[N];

void dfs1(int u, int p){
    f[u] = 1;
    for(int i = 0; i < (int)Adj[u].size(); i++){
        int v = Adj[u][i];
        if(v == p) continue;
        dfs1(v, u);
        f[u] = (f[u] * f[v]) % M;
    }
    f[u] = (f[u] + 1LL) % M;
}

void dfs2(int u, int p){
    vector<int> nodes;
    for(int i = 0; i < (int)Adj[u].size(); i++){
        int v = Adj[u][i];
        if(v == p) continue;
        nodes.pb(v);
    }
    pref[0] = suff[nodes.size() + 1] = 1;
    for(int i = 1; i <= (int)nodes.size(); i++){
        pref[i] = (pref[i - 1] * f[nodes[i - 1]]) % M;
    }
    for(int i = (int)nodes.size(); i >= 1; i--){
        suff[i] = (suff[i + 1] * f[nodes[i - 1]]) % M;
    }
    for(int i = 0; i < (int)nodes.size(); i++){
        g[nodes[i]] = (g[u] * pref[i]) % M;
        g[nodes[i]] = (g[nodes[i]] * suff[i + 2]) % M;
        g[nodes[i]] = (g[nodes[i]] + 1LL) % M;
    }
    for(int i = 0; i < (int)nodes.size(); i++){
        int v = nodes[i];
        dfs2(v, u);
    }
}

void process(){
    cin >> n >> M;
    for(int i = 1; i < n; i++){
        int x, y;
        cin >> x >> y;
        Adj[x].pb(y);
        Adj[y].pb(x);
    }
    dfs1(1, 1);
    g[1] = 1;
    dfs2(1, 1);
    for(int i = 1; i <= n; i++){
        cout << ((f[i] - 1LL + M) * g[i]) % M << "\n";
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    process();
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.