[题解][P5206][WC2019] 数树 (op = 1)

简要题意

给定 \(n, y\)。

一张图有 \(|V| = n\) 个点，现在给出两棵树 \(T_1=G(V, E_1)\) 和 \(T_2=G(V, E_2)\)。

定义这两棵树的权值 \(F(E_1, E_2)\) 为 \(y\) 的 \(G'=(V,E_1\cap E_2)\) 的联通块个数次方。

即 \(F(E_1, E_2) = y^{n - |E_1\cap E_2|}\)，给定 \(E_1\)，计算 \(\sum_{E_2} F(E_1, E_2)\)。

其中 \(n\le 10^5\)。答案对 \(998244353\) 取模。

解题思路

首先我们要找到一个合适的形式来表示我们的答案，部分枚举 \(S=E_1\cap E_2\)，则答案为：

\[\sum_{E_2} \sum_{S=E_1\cap E_2} y^{n-|S|} \]

其中 \(S=E_1\cap E_2\) 这个恰好的条件限制较强，考虑容斥将限制弱化为 \(S\subseteq E_1\cap E_2\).

不妨考虑这样一个容斥原理的式子：

\[f(S)=\sum_{T\subseteq S}\sum_{P\subseteq T}(-1)^{|T|-|P|}f(P) \]

代入到原来的式子中，得到：

\[\begin{aligned} &\sum_{E_2} \sum_{S=E_1\cap E_2} y^{n-|S|}\\ =&\sum_{E_2} \sum_{T\subseteq E_1\cap E_2} \sum_{P\subseteq T}(-1)^{|T|-|P|}y^{n-|P|}\\ =&\sum_{T\subseteq E_1}g(T)\sum_{P\subseteq T}(-1)^{|T|-|P|}y^{n-|P|}\\=&\sum_{T\subseteq E_1}g(T)y^{n-|T|}\sum_{P\subseteq T}(-y)^{|T|-|P|}\\ =&\sum_{T\subseteq E_1}g(T)\sum_{P\subseteq T}(-1)^{|T|-|P|}y^{n-|P|}\\=&\sum_{T\subseteq E_1}g(T)y^{n-|T|}\sum_{|P|=0}^{|T|}\binom{|T|}{|P|}(-y)^{|T|-|P|}\\ =&\sum_{T\subseteq E_1}g(T)\sum_{P\subseteq T}(-1)^{|T|-|P|}y^{n-|P|}\\=&\sum_{T\subseteq E_1}g(T)y^{n-|T|}(1-y)^{|T|}\\ \end{aligned} \]

其中 \(g(T)\) 表示包含边集 \(T\) 的 \(E_2\) 的个数。

假设 \(G=(V,T)\) 为一个由 \(k\) 个大小分别为 \(a_i\) 的连通块组成的森林，则：

\[g(T)=n^{k-2}\prod_{i=1}^ka_i \]

继续代入 (注意到 \(n=|T|+k\) )，得：

\[\begin{aligned} &\sum_{T\subseteq E_1}g(T)y^{n-|T|}(1-y)^{|T|}\\ =&\sum_{T\subseteq E_1}n^{k-2}\prod_{i=1}^ka_i\ y^k(1-y)^{n-k}\\ =&\frac{(1-y)^n}{n^2}\sum_{T\subseteq E_1}\prod_{i=1}^k\frac{ny}{1-y}\ a_i \end{aligned} \]

即一个大小为 \(a\) 的连通块为答案贡献一个乘积 Ka，其中 \(K = \frac{ny}{1-y}\)。

据此可以容易得到一个 \(O(n^2)\) 的 DP，\(f(x,i)\) 表示 \(x\) 的子树中，\(x\) 所在的连通块大小为 \(i\) 的答案。

考虑到这个贡献可以拆分表示为 \(\prod_{i=1}^k(K+K+K+\cdots K)\)，故合并两个大小分别为 \(x,y\) 的连通块时，新的贡献其实就是 \(K(x+y)\prod_{i\ne now}Ka_i\).

这样状态可以优化为 \(f(x,0/1)\) 表示 \(x\) 的子树中，当前连通块是否已经做出贡献。

那么转移就是 (前面是选边 \((x,y)\)，后面是不选)：

\[\begin{aligned} &f(x,1)=f(x,1)f(y,1)\ +\ f(x,1)f(y,0)+f(x,0)f(y,1)\\ &f(x,0)=f(x,0)f(y,1)\ +\ f(x,0)f(y,0) \end{aligned} \]

代码

void dfs(int x, int fx){
	siz[x] = 1, f[x] = coef, g[x] = 1;
	for(int i = head[x]; i; i = e[i].nx){
		int y = e[i].to; if(y == fx) continue;
		dfs(y, x);
		int sum = Mod((LL) f[x] * g[y] % mod + (LL) g[x] * f[y] % mod - mod);
		MOD(f[x] = (LL) f[x] * f[y] % mod + sum - mod);
		MOD(g[x] = (LL) g[x] * f[y] % mod + (LL) g[x] * g[y] % mod - mod);
	}
}

void solve(){
    coef = (LL) n * y % mod * qpow(1 - y + mod) % mod;
    dfs(1, 0);
    cout << (LL) f[1] * qpow(1 - y + mod, n) % mod * qpow((LL) n * n % mod) % mod << endl;
}