「WC 2019」数树
「WC 2019」数树
一道涨姿势的EGF好题，官方题解我并没有完全看懂，尝试用指数型生成函数和组合意义的角度推了一波。考场上只得了 44 分也暴露了我在数数的一些基本套路上的不足，后面的 \(\exp\) 是真的神仙，做不出来当然很正常，而且我当时也不怎么会多项式。
Task0
考虑公共边组成 \(k\) 个联通块，答案就是 \(y^k\) ，并查集维护一下即可，复杂度 \(\mathcal O(n\log n)\) 。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。code
namespace task0{
map<pair<int, int>, int> mp;
int fa[N];
inline int ask(int x){ return x == fa[x] ? x : fa[x] = ask(fa[x]); }
inline void solve(){
for(int i = 1; i <= n; i++) fa[i] = i;
for(int i = 1, x, y; i <= 2 * (n - 1); i++)
read(x), read(y), mp[make_pair(min(x, y), max(x, y))]++;;
for(map<pair<int, int>, int>::iterator it = mp.begin(); it != mp.end(); it++) if(it->second == 2)
if(ask(it->first.first) != ask(it->first.second)) fa[ask(it->first.first)] = ask(it->first.second);
int tot = 0;
for(int i = 1; i <= n; i++) if(fa[i] == i) tot++;
cout << Pow(Y, tot) << endl;
}
}Task1
考虑两棵树每有一条公共边，联通块个数就 \(-1\) ，不妨设一开始答案为 \(y^n\) ，每有一条公共边，其对答案的贡献就是 \(z=y^{-1}\) 。
先按照官方题解说的，引入组合恒等式
\[ z^k=(z-1+1)^k=\sum_{i=1}^k {k\choose i }(z-1)^i \]
考虑红树和蓝树的最终形态如果恰好有 \(k\) 条公共边，那么对答案的贡献就是 \(z^k\) ，考虑枚举这种形态的所有公共边的每一个子集，每一个大小为 \(i\) 的子集贡献为 \((z-1)^i\) ，就可以得到这个式子的组合意义。
不妨枚举一个大小为 \(i\) 的公共边集(一定是蓝树的一个边集)，然后考虑所有覆盖它的方案，其对答案的贡献就是 \((z-1)^i\) 乘上覆盖它的红树的数量。
假设当前有 \(i\) 条公共边，形成了 \(m=n-i\) 个联通块，其中第 \(i\) 个联通块大小为 \(a_i\) ，根据 \(prufer\) 经典结论 ，可以得到覆盖这个它的红树的数量。
\[ n^{m-2}\prod a_i \]
那么所有情况对答案的贡献和就是
\[ n^{-2}\sum_{m=1}^n(z-1)^{n-m}n^m\prod_{\sum_{i=1}^m a_i=n,a_i\geq1} a_i \]
考虑后面式子的组合意义是在每个联通块中恰好选出一个点的方案数，所以可以令 \(dp[u][0/1]\) 表示蓝树以 \(u\) 为根的联通块是否选出一个点的总贡献，此时每个联通块有 \(n\) 的贡献，每选一条公共边有 \(z\) 的贡献，讨论 \(u\) 的每个儿子是否和 \(u\) 在一个联通块即可，复杂度 \(O(n)\) 。
code
namespace task1{
int dp[N][2], Z;
vector<int> g[N];
inline void dfs(int u, int fa){
dp[u][0] = 1, dp[u][1] = n;
for(int i = 0; i < (int) g[u].size(); i++){
int v = g[u][i];
if(v == fa) continue;
dfs(v, u);
dp[u][1] = (1ll * dp[v][1] * dp[u][1] % P + 1ll * (Z - 1) * (1ll * dp[v][1] * dp[u][0] % P + 1ll * dp[v][0] * dp[u][1] % P) % P) % P;
dp[u][0] = (1ll * dp[v][1] * dp[u][0] % P + 1ll * dp[v][0] * dp[u][0] % P * (Z - 1) % P) % P;
}
}
inline void solve(){
Z = Pow(Y);
for(int i = 1, x, y; i < n; i++){
read(x), read(y);
g[x].push_back(y), g[y].push_back(x);
}
dfs(1, 0);
cout << 1ll * dp[1][1] * Pow(Y, n) % P * Pow(n, P - 3) % P << endl;
}
}Task 2
还是利用之前的组合恒等式，枚举一个公共边集 \(S\) ，算出其对答案的贡献。
考虑大小相同的公共边集的贡献是相同的，这一步等价于将 \(n\) 拆分成 \(m=n-|S|\) 个联通大小之和，每个联通块内部已经固定，计算所有拆分方式对答案的贡献，也就是：
\[ \sum_{m=1}^n(z-1)^{n-m}\sum_{\sum_{i=1}^{m}a_i=n,a_i\geq1}\dfrac{n!}{m!\prod a_i!} a_i^{a_i-2}\left(n^{m-2}\prod a_i\right)^2 \\ =(z-1)^nn^{-4}n!\sum_{m=1}^n\dfrac{(z-1)^{-m}n^{2m}}{m!}\sum_{\sum_{i=1}^ma_i=n,a_i\geq1}\prod\dfrac{a_i^{a_i}}{a_i!} \\ =(z-1)^nn^{-4}n!\sum_{m=1}^n\dfrac{1}{m!}\sum_{\sum_{i=1}^ma_i=n,a_i\geq1}\prod\dfrac{(z-1)^{-1}n^2a_i^{a_i}}{a_i!} \\ \]
大力观察这几个式子，第一个式子先枚举了划分的方案数以及联通块内部的连边方案，然后乘上了剩下边的方案(套用之前的 \(prufer\) 结论) 。考虑其组合意义可以看做有标号集合的拼接，将式子化成第三步的形式仍然满足这个组合意义。
单独考虑里面的集合拼接的式子里的每一个元素的生成函数。
\[ \prod\dfrac{(z-1)^{-1}n^2a_i^{a_i}}{a_i!} \\ f(x) = \sum_{i=1}^{\infty}\dfrac{(z-1)^{-1}n^2i^{i}}{i!}x^i \]
然后发现这个东西实际上要做的就是一个指数型生成函数的拼接，前面的 \(\dfrac{1}{m!}\) 是为了去掉集合拼接顺序的影响，把这个生成函数 \(\exp\) 一下就自然消掉了这个影响，所以式子就变成
\[ (z-1)^nn^{-4}n![x^n]\exp\left(\sum_{i=1}^{\infty}\dfrac{(z-1)^{-1}n^2i^{i}}{i!}x^i\right) \]
做一遍多项式 \(\exp\) ，注意 \(z = 1\) 也就是 \(y=1\)的时候 \((z-1)^{-1}\) 不存在，需要特判复杂度 \(\mathcal O(n \log n)\) 。
code
namespace task2{
int js[N], inv[N], ans[N], f[N];
inline void solve(){
if(Y == 1) return (void) (cout << 1ll * Pow(n, n - 2) * Pow(n, n - 2) % P << endl);
poly::init();
js[0] = inv[0] = 1;
for(int i = 1; i <= n; i++)
js[i] = 1ll * js[i-1] * i % P, inv[i] = Pow(js[i], P - 2);
int Z = Pow(Y, P - 2), c = 1ll * Pow(Z - 1, n) * Pow(n, P - 5) % P * js[n] % P;
int c2 = 1ll * n * n % P * Pow(Z - 1, P - 2) % P;
for(int i = 1; i <= n; i++) f[i] = 1ll * c2 * Pow(i, i) % P * inv[i] % P;
poly::getexp(f, ans, n + 1);
cout << 1ll * ans[n] * c % P * Pow(Y, n) % P;
}
} 
