最近的做题小结（二）

牛客小白月赛 127

E. Flower_Rainbow_and_Game

大致题意：给定一棵由 个节点构成的有根树，节点序号从 到 ，根节点序号为 ，定义 为点 到点 的最短距离，定义代价函数 ，其表达式为

其中 为 和 的最近公共祖先。

求解

思路：下面展示三种解法。

• 解法一（标答）：令 表示 所在的子树大小， 表示 子树中所有节点对 的距离之和。则该和式可分为两种情况

  • 情况 ：对于 中的每个子节点 ，二元组 的贡献都是 ，即这部分的求和为
  • 情况 ：对于 的情况，分别从 和 中 选取节点 和 ，则易得

  ​ 令 表示 之前遍历过的子节点的集合， 表示当前子节点 的节点集合，则贡献的总代价为

  遍历完 的贡献后进行状态转移，并将 的信息合并到 中即可。

  可以看到这种做法十分优雅，但难以理解，我花了足足半个小时看这个式子

• 解法二（我的做法）：看到题目要求的式子第一时间想到数形 dp，下面为大家详细介绍。

  假设题目要求的式子为

  怎么求呢？这是一道经典的数形 dp 模板题，其核心思想是考虑每条边的贡献。

  核心

  对于树上的每条边，它会被经过它的所有路径计算一次。

  这句话的言外之意是，每条边都会将树分成两个连通块，对于分别来自两个连通块的点，两者的距离路径必然会包含该条边，亦即该边对和式产生贡献。

  具体贡献为多少？这取决于两个连通块的各自节点数。设一侧有 个节点，则另一侧有 个节点，这条边的总贡献为

  则总贡献为

  接下来只需求每个节点分隔开的两侧节点数，求出任意一侧即可。

  由于是从根开始自上向下遍历，故记录已遍历的节点更易求得，一趟深搜即可，注意在深搜子树之后把子节点的 加到父节点上，再计算出该边的贡献。

  回到题目本身，其与上面的差异在于，若两个节点的最近公共祖先是其中一者，则距离修改为 。

  我们只需修正上式中祖先与后代二元组的距离，计算出差值即可。

  对于每个节点 ，记录其深度为 ，则它共有 个祖先，到每个祖先的原始距离从下到上依次为 ，故原始距离和为

  修正后新距离和应为

  故节点 的贡献差值为

  总贡献差值为

  在原有的基础上减掉这部分即可得到答案。

  注意

  减法时要先加模数，防止出现负数取模这类未定义行为。

• 解法三（gqb 大佬的解法）：伟大，无需多言，让我们用数学式子去完整表示这个问题。

  总和应有两部分构成：“祖先-后代”二元组与“非祖先-后代”二元组，对于第一部分，显然其值为 ，我们主要考虑“非祖先-后代”二元组的计算方式。

  对于两个节点 ，它们不满足“祖先-后代”关系，设 ，则有

  设节点 有 个子节点，记为 。

  对于每个子节点 ，定义 为以 为根的子树（包含本身），，，则 的所有后代集合（不包含自己）表示为

  记 ，表示所有后代的个数，，表示所有后代深度的总和。所以要求的第二部分可记为

  展开，有

  其中， 是满足 的 二元组的数量。

  现在我们逐步解决，对于 ，有

  由于每个节点 可以和其余 个点配对，故

  节点 同理，有

  对于

  其表示在 两节点在同一子树 下的配对，同前理，其值为

  同理，故

  对于 ，跨子树二元组数即为无限制二元组数与同子树二元组数的差，即

  故本题的最终解为