题解

问题分析

题目要求计算所有可能的生成树 ( T_2 ) 与原树 ( T_1 ) 的价值之和，价值定义为 ( |E_1 \cap E_2| \cdot 2^{|E_1 \cap E_2|} )。核心挑战是高效处理 ( n \le 2 \times 10^6 ) 的大规模输入，避免直接枚举所有生成树（数量为 ( n^{n-2} )，无法直接计算）。

核心思路

1. 树形动态规划（DP）：

   • 定义状态 ( dp[u][x][y] )，其中 ( u ) 是当前节点，( x ) 和 ( y ) 是二进制状态（分别表示子树中与原树边的交集情况相关的约束）。
   • 通过DFS遍历树 ( T_1 )，在每个节点合并子节点的DP状态，计算满足条件的生成树数量及对应的价值贡献。

2. 状态转移与合并：

   • 对于每个节点 ( u ) 及其子节点 ( v )，考虑边 ( (u, v) ) 是否被包含在生成树 ( T_2 ) 中，通过多重循环枚举状态组合（( x, y, p, q, o )），更新当前节点的DP状态。
   • 状态转移中包含模运算，确保结果在 ( 998244353 ) 范围内。

3. 结果计算：

   • 最终DP状态 ( dp[1][1][1] ) 存储了关键中间结果，结合快速幂计算模逆元（用于除法运算），得到最终价值之和。

代码解析

1. 树形DP状态定义：

   • ( dp[u][0][0] ) 和 ( dp[u][1][0] ) 初始化表示节点 ( u ) 自身的基础状态（如包含自身的生成树计数）。
   • 状态 ( x, y ) 用于跟踪子树中与原树边的交集数量及相关约束，确保生成树的无环性。

2. DFS与状态合并：

   • 递归遍历子树，对每个子节点的DP状态进行合并。通过多重循环枚举所有可能的状态组合，累加符合条件的生成树数量。
   • 合并过程中使用临时数组 ( fg ) 存储中间结果，避免覆盖当前节点的DP状态。

3. 模运算与快速幂：

   • 快速幂函数 ( ksm ) 用于计算模逆元，处理除法运算（如代码中除以 ( n^2 ) 的操作）。
   • 所有运算均在模 ( 998244353 ) 下进行，确保数值不溢出且符合题目要求。

总结

该解法通过树形DP高效计算生成树的价值之和，利用状态压缩和模运算处理大规模输入。核心是通过动态规划跟踪生成树与原树的边交集情况，避免直接枚举所有生成树，时间复杂度为 ( O(n) )（因每个节点的状态转移是常数级），适用于 ( n \le 2 \times 10^6 ) 的数据范围。