Subtree - edpc v

#全方位木dp

コード
https://atcoder.jp/contests/dp/submissions/10244725

まず, 頂点 0 を根とした木の答えを求める.

void dfs(int v, int p) {
  ll ret = 1;
  for (edge& e : G[v]) {
    if (e.to == p) continue;
    dfs(e.to, v);
    (ret *= dp[e.to] + 1) %= m;
  }
  dp[v] = ret;
}

各頂点 i に関し, 部分木の答え (部分木の根を黒としたときの組み合わせ) + 1 のかけ合わせ
+ 1 というのは, 部分木がすべて白の場合
i の下連続で黒になってないとダメ

次に, 頂点 0 だけでなく, 各頂点 i を根とした答えを求める.
計算量の関係で, 先ほど求めた dp を使い回す

void dfs2(int v, int Dpar, int p) {
  int n2 = sz(G[v]);
  vector<ll> mul(n2 + 1, 1), mul2(n2 + 1, 1);
  ll ret = 1;

  rep(i, n2) {
    edge e = G[v][i];
    if (e.to == p) {
      (ret *= Dpar + 1) %= m;
      if (i) (mul[i - 1] *= Dpar + 1) %= m;
      (mul2[i + 1] *= Dpar + 1) %= m;
    } else {
      (ret *= dp[e.to] + 1) %= m;
      if (i) (mul[i - 1] *= dp[e.to] + 1) %= m;
      (mul2[i + 1] *= dp[e.to] + 1) %= m;
    }
  }
  for (int i = n2 - 2; i >= 0; --i) (mul[i] *= mul[i + 1]) %= m;
  rep3(i, 1, n2) (mul2[i] *= mul2[i - 1]) %= m;
  rep(i, n2) (mul[i] *= mul2[i]) %= m;

  ans[v] = ret;
  rep(i, n2) {
    edge e = G[v][i];
    if (e.to == p) continue;
    dfs2(e.to, mul[i], v);
  }
}

親方向を除いてそのまま部分木の答えを使える
親方向は Dpar に持たせる

遷移先の Dpar の計算は, その頂点 i を根とする木の答えからその部分木の答え + 1 を割ったもの
(その部分木の答えを除いたもの)

mod を取るので割り算はダメ
逆元を使いたいが m は素数とは限らない
累積積を用いる

参考
https://kyopro-friends.hatenablog.com/entry/2019/01/12/231106