Subtree [Educational DP Contest / DP まとめコンテスト V]

https://atcoder.jp/contests/dp/tasks/dp_v

前提知識

• 全方位木DP

解説

https://atcoder.jp/contests/dp/submissions/3955506

全方位木DPをする。
dfs1で0を根として普通に木DPをする。
次に、dfs1で作ったDPを改変しながら、dfs2で全ての頂点を根として答えを計算する。
全方位木DPの様式であり、パターン化されている。
　
dfs1関数。
木DPは
dp[cu] := 頂点cuの部分木の塗り方において、頂点cuが黒色に塗られていて、黒色の頂点が全て連結である塗り方の組み合わせ
で作る。
更新式は頂点cuの子供をc1,...,cNとすると、dp[cu] = (dp[c1]+1)*...*(dp[cN]+1)である。+1しているのは、頂点c1が白である状態を示す（根が白ならば部分木は全て白色なので1通り）。
頂点0が黒である場合の答えはこれで求められる。
この関数が分からない場合は、全方位木DPの前に木DPを学ぶことを勧める。
　
dfs2関数。
全方位木DPをするが、大切なのは、
「『頂点cuの処理時はDPが頂点cuを根としたときの状態になっている』ことを保つこと」
具体的には頂点cuから頂点toに遷移するときは、dp[cu]を頂点toを親としたときの値に変換してから遷移する。
dp更新は、頂点cuの子供をc1, ..., cNとすると、dp[cu] = (dp[c1] + 1)*...*(dp[cN] + 1)という感じなので、例えばc3に遷移するときはdp[cu] = (dp[c1]+1)*(dp[c2]+1)*(dp[c4]+1)*...*(dp[cN]+1)*(dp[parent]+1)として遷移する。
この計算を高速に行うには
lft[i] := (dp[c1]+1)*...*(dp[ci]+1)
rht[i] := (dp[ci]+1)*...*(dp[cN]+1)
を予め計算すると、高速に計算可能。

int N;
vector<int> E[101010];
//---------------------------------------------------------------------------------------------------
mint dp[101010];
void dfs1(int cu, int pa = -1) {
    dp[cu] = 1;
    fore(to, E[cu]) if (to != pa) {
        dfs1(to, cu);
        dp[cu] *= dp[to] + 1;
    }
}
//---------------------------------------------------------------------------------------------------
mint ans[101010];
void dfs2(int cu, int pa = -1) {
    ans[cu] = 1;
    fore(to, E[cu]) ans[cu] *= dp[to] + 1;
 
    int n = E[cu].size();
    vector<mint> lft(n), rht(n);
    rep(i, 0, n) lft[i] = rht[i] = dp[E[cu][i]] + 1;
    rep(i, 1, n) lft[i] *= lft[i - 1];
    rrep(i, n - 2, 0) rht[i] *= rht[i + 1];
 
    rep(i, 0, n) if (E[cu][i] != pa) {
        dp[cu] = 1;
        if (i) dp[cu] *= lft[i - 1];
        if (i + 1 < n) dp[cu] *= rht[i + 1];
        dfs2(E[cu][i], cu);
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> MOD;
    rep(i, 0, N-1) {
        int x, y; cin >> x >> y;
        x--; y--;
        E[x].push_back(y);
        E[y].push_back(x);
    }
 
    dfs1(0);
    dfs2(0);
 
    rep(i, 0, N) printf("%d\n", ans[i].get());
}