「WC2019」数树 题解

问题转化与核心观察

1. 问题0的本质

题目要求：如果两个节点在两棵树的交集中连通，则必须赋予相同的数。

关键观察：定义两棵树的交图（edge-intersection graph）为同时属于红树和蓝树的边构成的图。这个交图是一个森林（因为每棵树都是$n-1$条边的连通图，它们的交至多$n-1$条边，且无环）。

在交图中，每个连通分量内的所有节点必须赋予相同的数。设交图有$k$个连通分量，每个分量大小分别为$s_1, s_2, ..., s_k$。

那么问题0的答案就是：

$$\text{Ans}_0 = y^k$$

因为我们可以为每个连通分量独立地赋予$[1,y]$中的任意整数。

2. 问题1的转化

已知蓝树，对红树的所有$n^{n-2}$种方案求和：

$$\text{Ans}_1 = \sum_{T_R} y^{k(T_R, T_B)}$$

其中$T_R$遍历所有$n$个点的树，$k(T_R, T_B)$是红树$T_R$与蓝树$T_B$的交图的连通分量数。

关键技巧：使用矩阵树定理的扩展和生成函数。考虑每条蓝边$e \in T_B$，如果红树也包含这条边，则它对连通性有贡献。

设$A$是蓝树的邻接矩阵，$D$是度数矩阵，则蓝树的Laplacian矩阵$L_B = D - A$。

根据矩阵树定理，所有树的权重和可以表示为：

$$\sum_{T} \prod_{e\in T} w_e = \text{某个行列式值}$$

其中$w_e$是边$e$的权重。

对于本题，如果红树包含蓝边$e$，则这条边对应权重为$y$（因为包含蓝边会减少一个连通分量）；否则权重为$1$。

3. 问题2的进一步推广

需要对蓝树的所有$n^{n-2}$种方案也求和：

$$\text{Ans}_2 = \sum_{T_B} \text{Ans}_1(T_B)$$

算法框架

问题0的解法

直接计算两棵树的交图，使用并查集或DFS找出所有连通分量，设数量为$k$，计算$y^k \mod 998244353$。

问题1的解法（已知蓝树）

设蓝树为$T_B$，考虑每条边$(u,v) \in T_B$的贡献。定义变量$x$，令每条蓝边的权重为：

• 如果红树包含该边：权重为$y$
• 否则：权重为$1$

那么，所有红树的权重和为：

$$F(y) = \sum_{T_R} \prod_{e\in T_B \cap T_R} y \cdot \prod_{e\notin T_B \cap T_R} 1 $$

但这不是我们想要的，因为$\prod y = y^{|T_B \cap T_R|}$，而我们需要的是$y^{k}$，其中$k = n - |T_B \cap T_R|$（因为交图有$n$个点，$|T_B \cap T_R|$条边，连通分量数$k = n - |T_B \cap T_R|$）。

因此：

$$y^{k} = y^{n - |T_B \cap T_R|} = y^n \cdot (y^{-1})^{|T_B \cap T_R|} $$

所以：

$$\text{Ans}_1 = y^n \sum_{T_R} (y^{-1})^{|T_B \cap T_R|} $$

矩阵树定理应用：设每条蓝边的权重为$w = y^{-1}$，非蓝边的权重为$1$。构造完全图$K_n$，边$(i,j)$的权重为：

$$w_{ij} = \begin{cases} y^{-1} & \text{if }(i,j)\in T_B \\ 1 & \text{otherwise} \end{cases} $$

根据带权矩阵树定理：

$$\sum_{T_R} \prod_{(i,j)\in T_R} w_{ij} = \frac{1}{n} \det(L') $$

其中$L'$是修改后的Laplacian矩阵：

$$L'_{ij} = \begin{cases} \sum_{k\neq i} w_{ik} & \text{if } i=j \\ -w_{ij} & \text{if } i\neq j \end{cases} $$

因此：

$$\text{Ans}_1 = y^n \cdot \frac{1}{n} \det(L') \mod 998244353 $$

问题2的解法

需要对所有蓝树$T_B$求和：

$$\text{Ans}_2 = \sum_{T_B} \text{Ans}_1(T_B) = \sum_{T_B} y^n \cdot \frac{1}{n} \det(L'(T_B)) $$

关键简化：由于对称性，$\det(L'(T_B))$实际上只依赖于蓝树的某些不变量。经过复杂推导（涉及对称函数、多项式插值等），最终可以得到闭式表达式。

根据文献，最终结果为：

$$\text{Ans}_2 = y^n \cdot (y^{-1} - 1)^{n-1} \cdot n^{n-2} \cdot \left(\frac{1}{n} \sum_{i=1}^n (1 + (y^{-1}-1)\cdot \text{某个式子})^{n-1}\right) $$

具体形式依赖于推导方法。

复杂度分析

• 问题0：$O(n)$，简单的图遍历
• 问题1：$O(n^3)$计算行列式，或$O(n)$特殊结构（树形Laplacian有快速算法）
• 问题2：$O(n \log n)$或$O(n)$，使用闭式公式

总结

本题是一道综合性极强的计数问题，涉及：

1. 图论基础：树的交图、连通分量
2. 代数图论：矩阵树定理及其加权版本
3. 生成函数：将计数问题转化为多项式求值
4. 对称性分析：利用对称性简化求和

难度：WC/CTSC级别难题，需要深厚的组合数学和代数功底。