Distributing Integers [AtCoder Beginner Contest 160 F]

https://atcoder.jp/contests/abc160/tasks/abc160_f

前提知識

• 全方位木DP

解説

https://atcoder.jp/contests/abc160/submissions/11325358

全方位木DPが分かっていないと解けない。
この問題で全方位木DPを学ぶには少し問題がややこしい。
入門問題としては「Educational DP Contest / DP まとめコンテスト V Subtree」あたりがいいだろう。
これの解説を探して学んでもいいし、「全方位木DP」や「Rerooting」で検索して解説を読むのもいいだろう。

さて、まずは全方位木DPでありがちな、ある頂点を根とした時の木DPをまずは考えよう。
部分問題である。
dp[cu] := 頂点cuを根とした部分木にルールにしたがって1,2,3,...のように番号をつける組み合わせ
とりあえず、こう定義すればよさそう。
これを起点に考えると、更新式が見える。
頂点cuの直接の子供をto1, to2, ..., toMとして、頂点cuを根とした部分木の頂点数をcnt[cu]とすると、
dp[cu] = dp[to1] * dp[to2] * ... * dp[toM] * !(cnt[to1] + cnt[to2] + ... + cnt[toM]) / (!cnt[to1] * !cnt[to2] * ... * !cnt[toM])
こうなる。

例えば、ABC,abcという部分木の書き込み方をマージするときに、根は1なので、1ABCabcと書いてもいいし、
1AaBbCcとか1ABabcCみたいにしても大丈夫。つまり、部分木の書き込み方の順番は変えずにマージする感じ。
更新式の前半のdp[to1] * dp[to2] * ... * dp[toM]は各部分木での書き込み方で、
後半の!(cnt[to1] + cnt[to2] + ... + cnt[toM]) / (!cnt[to1] * !cnt[to2] * ... * !cnt[toM])でマージの場所の組み合わせを決めている。
後半部分は、これである。
【高校数学A】同じものを含む順列 n!/p!q!r! | 受験の月

こうすることで木DP部分は出来上がったので、全方位木DPに変換していく。
この変換作業が難しいのだが、差分だけを計算するように頑張って計算する。
0割りしてしまいそうな気もするのだが、サボって逆元使って計算すると通る。

Comb<mint, 401010> com;
int N;
vector<int> E[201010];
//---------------------------------------------------------------------------------------------------
mint dp[201010];
int cnt[201010];
void dfs1(int cu, int pa = -1) {
    dp[cu] = 1;

    int cn = 0;
    fore(to, E[cu]) if (to != pa) {
        dfs1(to, cu);
        cn += cnt[to];
        dp[cu] *= dp[to] * com.ifac[cnt[to]];
    }

    dp[cu] *= com.fac[cn];
    cnt[cu] = cn + 1;
}
//---------------------------------------------------------------------------------------------------
mint ans[201010];
void dfs2(int cu, int pa = -1) {
    int cn = 0;
    ans[cu] = 1;
    fore(to, E[cu]) {
        cn += cnt[to];
        ans[cu] *= dp[to] * com.ifac[cnt[to]];
    }
    ans[cu] *= com.fac[cn];

    fore(to, E[cu]) if (to != pa) {
        cnt[cu] = cn - cnt[to] + 1;
        dp[cu] = ans[cu] * com.ifac[cn] / dp[to] * com.fac[cnt[to]] * com.fac[cn - cnt[to]];
        dfs2(to, cu);
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N - 1) {
        int a, b; cin >> a >> b;
        a--; b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }

    dfs1(0);
    dfs2(0);

    rep(i, 0, N) printf("%d\n", ans[i].get());
}