Statement
有 \(n\) 个节点, 分别用红线, 蓝线连成两棵树. 用 \(y\) 种颜色给节点染色, 规定如果一条边在两棵树中同时出现, 那么边两端的点的颜色必须相同.
- Task #1: 给定两棵树, 求染色方案.
- Task #2: 给定其中一棵树, 求对于另一棵树的每一种形态的染色方案数之和.
- Task #3: 两棵树的形态都没有确定, 求对于所有情况的染色方案数之和.
- (\(n\le 10^5\))
- Solution
- Task #1
计算有多少条公共边即可.
Task #2
如果有 \(i\) 条公共边, 那么贡献为 \(y^{n-i}\). 设 \(z=y^{-1}\), 贡献为 \(y^n z^{i}\), 考虑计算 \(z^i\), 最后乘上 \(y^n\).
\[ \begin{aligned} z^i &= (z-1+1)^i \&= \sum_{j=0}^i (z-1)^j \binom{i}{j} \end{aligned} \]
于是我们对于边集 \(E\) 的每个子集 \(E'\) 的贡献为 \((z-1)^{|E'|}\).
对于一个公共边的边集的选取方案, 将边连起来, 形成了很多个连通块, 大小为 \(a_1\dots a_m\), 那么贡献为:
\[ (z-1)^{n-m} n^{m-2} \prod_{i=1}^m a_i \]
\((z-1)^{n-m}\) 为贡献, \(n^{m-2}\prod_{i=1}^m a_i\) 为 \(n\) 个点,\(m\) 个块的树的个数.
上面这个式子的组合意义为在每个块中选一个点的方案数, 树形 DP 即可, 时间复杂度 \(O(n)\).
Task #3
类似 Task2 的思路, 枚举至少有 \(n-m\) 条公共边, 即 \(m\) 个连通块的方案数:
- \[ \begin{
- aligned
- } g_m &= \sum_{
- \sum\limits_{
- i=1
- }^m a_i = n
- } \sum_{
- j=1
- }^m \binom{
- \sum_{
- k=1
- }^j a_k - 1
- }{
- a_j-1
- } \left(n^{
- m-2
- } \prod_{
- i=1
- }^m a_i\right)^2 \prod _{
- i=1
- }^m a_i ^ {
- a_i - 2
- } \&= \sum_{
- \sum\limits_{
- i=1
- }^m a_i = n
- } \sum_{
- j=1
- }^m \binom{
- \sum_{
- k=1
- }^j a_k - 1
- }{
- a_j-1
- } n^{
- 2(m-2)
- } \prod_{
- i=1
- }^m a_i^{
- a_i
- } \end{
- aligned
- } \]
- \[ \begin{
- aligned
- } ans &= \sum_m g_{
- m
- } \times (z - 1)^{
- n-m
- } \&= \sum_{
- \sum\limits_{
- i=1
- }^m a_i = n
- } \sum_{
- j=1
- }^m \binom{
- \sum_{
- k=1
- }^j a_k - 1
- }{
- a_j-1
- } n^{
- 2(m-2)
- } \prod_{
- i=1
- }^m a_i^{
- a_i
- } (z-1)^{
- n-m
- }\\end{
- aligned
- } \]
设 \(f_k\) 表示当前已经处理了 \(k\) 个块, 那么有转移:
\[ f_k = \begin{cases} n^{-4}(z-1)^n &,k=0 \(z-1)^{-1} n^2\sum_{i=1}^k f_{k-i} \binom{k-1}{i-1} i^i &,k=1 \end{cases} \]
写成卷积的形式:
\[ f_k = (z-1)^{-1}(k-1)!n^2 \sum_{i=1}^k \frac{f_{k-i}}{(k-i)!}\times\frac{i^i}{(i-1)!} \]
分治 FFT 即可, 时间复杂度 \(O(n\log^2n)\).
- namespace Subtask0 {
- map<LL, int> mp;
- void Main() {
- For(i, 1, n - 1) {
- int x = read<int>(), y = read<int>();
- mp[(LL)x * 1e9 + y] = 1;
- }
- int ans = 0;
- For(i, 1, n - 1) {
- int x = read<int>(), y = read<int>();
- if (mp[(LL)x * 1e9 + y]) ++ ans;
- }
- printf("%d\n", fpm(y, n - ans));
- }
- }
- namespace Subtask1 {
- int beg[MAXN], v[MAXN <<1], nex[MAXN << 1], e = 1;
- void add(int uu, int vv) {
- v[++ e] = vv, nex[e] = beg[uu], beg[uu] = e;
- }
- int dp[MAXN][2];
- void DFS(int u, int pa) {
- dp[u][0] = (LL)fpm(n, MOD - 2) * fpm(z - 1, n - 1) % MOD;
- for (int i = beg[u]; i; i = nex[i])
- if (v[i] != pa) {
- DFS(v[i], u);
- int t0 = dp[u][0], t1 = dp[u][1];
- dp[u][0] = (LL)t0 * dp[v[i]][1] % MOD * n % MOD * n % MOD * fpm(fpm(z - 1), n) % MOD;
- dp[u][1] = (LL)t1 * dp[v[i]][1] % MOD * n % MOD * n % MOD * fpm(fpm(z - 1), n) % MOD;
- (dp[u][0] += (LL)t0 * dp[v[i]][0] % MOD * n % MOD * fpm(fpm(z - 1), n - 1) % MOD) %= MOD;
- (dp[u][1] += (LL)t0 * dp[v[i]][1] % MOD * n % MOD * fpm(fpm(z - 1), n - 1) % MOD) %= MOD;
- (dp[u][1] += (LL)t1 * dp[v[i]][0] % MOD * n % MOD * fpm(fpm(z - 1), n - 1) % MOD) %= MOD;
- }
- (dp[u][1] += dp[u][0]) %= MOD;
- }
- void Main() {
- if (y == 1) {
- printf("%d\n", fpm(n, n - 2));
- return;
- }
- For(i, 2, n) {
- int u = read<int>(), v = read<int>();
- add(u, v), add(v, u);
- }
- DFS(1, 0);
- printf("%lld\n", (LL)fpm(y, n) * dp[1][1] % MOD);
- }
- }
- namespace Subtask2 {
- int f[MAXN <<1];
- void cdqFFT(int l, int r) {
- static int A[MAXN << 1], B[MAXN << 1];
- if (l == r) {
- if (!l) f[0] = (LL)fpm(fpm(n), 4) * fpm(z_, n) % MOD;
- else f[l] = (LL)f[l] * iz_ % MOD * fac[l - 1] % MOD;
- return;
- }
- int mid = (l + r)>> 1, len = 1, pt = 0;
- cdqFFT(l, mid);
- while (len < mid - l + 1) ++ pt, len <<= 1;
- Rep(i, len) {
- A[i] = (LL)f[l + i] * ifac[l + i] % MOD;
- if (i) B[i] = (LL)fpm(i, i) * ifac[i - 1] % MOD * n % MOD * n % MOD;
- }
- For(i, len, len * 2 - 1) {
- A[i] = 0;
- B[i] = (LL)fpm(i, i) * ifac[i - 1] % MOD * n % MOD * n % MOD;
- }
- calcrev(len << 1, pt + 1);
- NTT(A, len << 1, 1), NTT(B, len << 1, 1);
- Rep(i, len << 1) A[i] = (LL)A[i] * B[i] % MOD;
- NTT(A, len << 1, -1);
- For(i, mid + 1, r) inc(f[i], A[i - l]);
- cdqFFT(mid + 1, r);
- }
- void Main() {
- if (y == 1) {
- printf("%d\n", fpm(n, 2 * n - 4));
- return;
- }
- InitFac(n);
- z_ = z - 1, iz_ = fpm(z_);
- cdqFFT(0, N - 1);
- printf("%lld\n", (LL)f[n] * fpm(y, n) % MOD);
- }
- }
[WC2019] 数树
来源: http://www.bubuko.com/infodetail-2948565.html