WC2019

好题啊！

数树

• ( ext{opt = 0, 6 pts.})

显然答案为 (y^{n-|E_1∩E_2|}) 。

• ( ext{opt = 1, 47 pts.})

[sum_{E_2}y^{n-|E_1∩E_2|} ]

考虑该容斥式：(f(S)=sumlimits_{Tsubset S}sumlimits_{Psubset T}(-1)^{|T|-|P|}f(P)) ，则：

[sum_{E_2}sum_{Tsubset E_1∩E_2}sum_{Psubset T}(-1)^{|T|-|P|}y^{n-|P|} ]

令 (g(T)) 表示包含 (T) 的 (E_2) 个数。

[sum_{Tsubset E_1}g(T)sum_{Psubset T}(-1)^{|T|-|P|}y^{n-|P|} ]

[sum_{Tsubset E_1}g(T)y^{n-|T|}sum_{Psubset T}(-y)^{|T|-|P|} ]

[sum_{Tsubset E_1}g(T)y^{n-|T|}sum_{k=0}^{|T|}inom{|T|}{k}1^k(-y)^{|T|-k} ]

[sum_{Tsubset E_1}g(T)y^{n-|T|}(1-y)^{|T|} ]

考虑一个定理：给定 (n) 个点的森林，有 (k) 个连通分量，第 (i) 个连通分量的大小为 (a_i) ，则由 ( ext{prufer}) 序列得：生成树的个数为 (n^{k-2}prodlimits_{i=1}^{k}a_i) 。

代回原式，记 (k=n-|T|) ，表示连通分量个数：

[sum_{Tsubset E_1}y^k(1-y)^{n-k}n^{k-2}prod_{i=1}^{k}a_i ]

[frac{(1-y)^n}{n^2}sum_{Tsubset E_1}prod_{i=1}^{k}frac{ny}{1-y}a_i ]

发现一个大小为 (a_i) 的连通分量对答案的贡献为 (Ka_i) ，其中 (K=frac{ny}{1-y}) 为一个常量。

考虑贡献的组合意义，大小为 (a_i) 的连通分量贡献相当于在这个连通分量重选取一个点，产生 (K) 的乘积贡献。

据此，可进行 (dp) ：(mathrm{f[u][0/1]}) 表示在 (u) 的子树中，当前连通分量是否已经做出贡献的答案。这里为了方便转移，当前连通分量若已做出贡献，就计入答案。

int f[N][2], K;
void dfs(int u, int fa) {
  f[u][0] = 1, f[u][1] = K;
  for (auto v: adj[u]) {
    if (v == fa) continue; 
    dfs(v, u);
    f[u][1] = (1ll * f[u][0] * f[v][1] + 1ll * f[u][1] * f[v][0] + 1ll * f[u][1] * f[v][1]) % mod;
    f[u][0] = (1ll * f[u][0] * f[v][0] + 1ll * f[u][0] * f[v][1]) % mod;
  }
} 

• ( ext{opt = 2, 47 pts.})

[sum_{E_1}sum_{E_2}y^{n-|E_1∩E_2|} ]

[sum_{E_1}sum_{E_2}sum_{Tsubset E_1∩E_2}sum_{Psubset T}(-1)^{|T|-|P|}y^{n-|P|} ]

这一段类似 ( ext{opt = 2}) ，直接快进：

[sum_{T}g^2(T)y^{n-|T|}(1-y)^{|T|} ]

[sum_{T}y^k(1-y)^{n-k}n^{2(k-2)}prod_{i=1 }^{k}a_i^2]

[frac{(1-y)^n}{n^4}sum_{T}prod_{i=1}^{k}frac{n^2y}{1-y}a_i^2 ]

换个角度考虑，每个连通分量是无序的，相当于有 (n) 个有标号小球扔进 (k) 个无标号盒子，盒子不为空。

对于一个装有 (a) 个球的盒子，一个生成树对其贡献为 (frac{n^2y}{1-y}a^2) 作为乘积，有 (a^{a-2}) 个生成树，因此总乘积贡献为 (frac{n^2y}{1-y}a^a) 。

显然，总方案的 (EGF) 等于 (exp) 单个盒子的 (EGF) ，即：

[F=sumlimits_{i=1}^{infty}frac{n^2y}{1-y}i^ifrac{x^i}{i!} ]

[G=exp(F) ]

答案即为：

[frac{(1-y)^n}{n^4}n![x^n]G ]

套多项式 (exp) 即可。

时间复杂度 (O(nlogn)) 。