题解：AT_abc160_f [ABC160F] Distributing Integers

· · 题解

前言

做 DP 专题遇到了这题，遂来写一下题解。

思路与方程可以在一刻钟内推出。

个人感觉代码不是特别好写。

题意

有一棵包含 N 个顶点的树，顶点编号为 1 到 N。这棵树的第 i 条边连接了顶点 a_i 和顶点 b_i。

对于 k=1,\ldots,N，请解决以下问题：

  • 按照如下步骤，在树的每个顶点上写一个整数。
    • 首先，在顶点 k 上写 1。
    • 然后依次将 2,\ldots,N 写到顶点上。每次选择要写入的顶点时，需满足以下条件：
      • 该顶点尚未被写入整数，且与已写入整数的顶点相邻。如果有多个满足条件的顶点，则从中随机选择一个。
  • 求所有可能的整数写法的数量，并对 10^9+7 取模。

Sol

换根 DP。

先考虑以 1 为根时的转移。

设以 1 为根时，以 u 为根的子树内的答案值为 f_u，以 u 为根的子树大小为 size_u，u 的儿子集合为 son_u，u 的儿子数量为 d_u。

树形 DP 转移一般从儿子子树转移到当前子树，于是考虑这个过程怎么刻画。

发现其实就是每次随机一个儿子子树走，求方案数而已，而进到儿子子树里的方案数难以刻画。

儿子子树的方案数难以刻画，不妨假设儿子子树内方案确定。这时候就可以不管儿子子树了。

儿子子树的相对操作次序确定了，子树就可以看作一个操作队列，每次即从任意一个队首取出一个元素进行标号。

选择队首的顺序序列，可以看作儿子子树的虚构的编号组成的序列，而操作只是对这些序列的每个位置对应一个子树编号而已。设若儿子子树编号分别为 v_1,v_2,\cdots,v_d，那么选择队首的顺序序列，其实就是一个由 size_{v_i} 个 v_i 组成（1\le i\le d）的多重集，而在“假设儿子子树内方案确定”这个大前提下的操作方案数，其实就是这个多重集的排列数罢了。

刚刚提到大前提是“假设儿子子树内方案确定”，那如果不确定呢？此时可以将各个儿子子树内的答案值乘入，就得到了正确的父亲子树内的答案值。

用形式化的公式，就是：

f_u=\binom{\sum_{v\in son_u}size_v}{size_{v_1},size_{v_2},\cdots,size_{v_{d_u}}}\prod_{v\in son_u}f_v

设 ans_u 表示以 u 为根时的答案（有 ans_1=f_1）。

由这个公式，也可以得到根由父亲 u 转移到儿子 v 时的公式：

ans_v=\frac{ans_u\times size_v}{n-size_v}

:::success[Code]{open}

#include <bits/stdc++.h>
#define sfr return cerr << "safe\n", 0;
#define sf_void return cerr << "safe\n", void();
using namespace std;
using ll = long long;
using i128 = __int128;
using pr = pair<int, int>;
using prt = tuple<int, int>;
using tpt = tuple<int, int, int>;
const int N = 2e5 + 10, mod = 1e9 + 7;

auto fpw(ll x, int k) {
    ll ret = 1;
    while (k) {
        if (k & 1) (ret *= x) %= mod;
        k >>= 1;
        (x *= x) %= mod;
    }
    return ret;
}

ll fac[N], inv[N];

auto init() {
    fac[0] = 1;
    for (int i = 1; i < N; ++i) {
        fac[i] = fac[i - 1] * i % mod;
    }
    inv[N - 1] = fpw(fac[N - 1], mod - 2);
    for (int i = N - 1; i >= 1; --i) {
        inv[i - 1] = inv[i] * i % mod;
    }
}

auto C(int n, int m) { return fac[n] * inv[m] % mod * inv[n - m] % mod; }

int n, siz[N];
ll ans[N], f[N], invf[N];
vector<int> E[N];

auto dfs1(int u, int fa) -> void {
    siz[u] = 1;
    ll tmp1 = 1, tmp2 = 1;
    for (auto &v : E[u]) {
        if (v == fa) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        (tmp1 *= f[v]) %= mod;
        (tmp2 *= fac[siz[v]]) %= mod;
    }
    f[u] = tmp1 * fac[siz[u] - 1] % mod * fpw(tmp2, mod - 2) % mod;
    invf[u] = fpw(f[u], mod - 2);
}

auto dfs2(int u, int fa) -> void {
    for (auto &v : E[u]) {
        if (v == fa) continue;
        // auto tmp = ans[u] * fac[siz[v]] % mod * invf[v] % mod * fac[n - siz[v] - 1] % mod * inv[n - 1] % mod;
        // ans[v] = f[v] * inv[siz[v] - 1] % mod * inv[n - siz[v]] % mod * fac[n - 1] % mod * tmp % mod;
        ans[v] = ans[u] * siz[v] % mod * fpw(n - siz[v], mod - 2) % mod;
        dfs2(v, u);
    }
}

auto main() -> signed {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    init();
    cin >> n;
    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v, E[u].emplace_back(v), E[v].emplace_back(u);
    }
    dfs1(1, 0), ans[1] = f[1], dfs2(1, 0);
    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << "\n";
    }
    // cerr << fac[n] << "\n";
}

:::