DP雑記⑭

木DPが苦手なので、克服するために木DPの問題を解いている。
そして先ほど、Typical DP Contest N - 木を解説ありで解いた。数ヶ月前は解説を読んでも理解できずに諦めていたので、多少は成長しているよう。
自分なりの木DPの書き方を確立できているのも大きい。

自分なりの木DPの書き方というのは、一度のDFSで色々なことを済ませるというもの。
そして、DFSは計算結果を戻り値として返さずに、配列に入れるようにする。
あと細かい部分では、if (e.to == p) continue;ではなくif (e.to != p)と書く。

次のコードは、先ほどの問題に提出したコードの主要部分。

vector<int> co(N);
vector<mint> dp(N);
auto dfs = [&](auto dfs, int u, int p) -> void {
  int acc_cnt = 0;
  mint ret = 1;
  each(e, g[u]) if (e.to != p) {
    dfs(dfs, e.to, u);
    int c = co[e.to] + 1;
    acc_cnt += c;
    ret = mc.com(acc_cnt, c) * dp[e.to] * ret;
  }
  co[u] = acc_cnt;
  dp[u] = ret;
};
mint ans = 0;
rep(i, N) {
  dfs(dfs, i, -1);
  ans += dp[i];
}
ans /= 2;
cout << ans << endl;

この書き方は書きやすいので、これからもこの書き方をしていく。