Editorial for Atcoder Educational DP Contest V - Subtree


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: 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();
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.