NC2025winter Round5 G

题目大意

一颗树，有点权，求三元组数量，其中,且在到的路径上。

分析

由于是求三元组，我们可以枚举节点(这个更特殊一些)，然后计算合法的对的数量。 如果是暴力枚举，我们需要以每个点为根搜一遍所有子树并且统计信息，时间复杂度为。 我们考虑使用dsu on tree的思想得到一个较优的枚举方案，同时想出一个合适的计算贡献方案，可以利用继承重子的信息。这里我们可以随意指定一个根，下面所说子树均是以一个固定点为根的子树。 统计时，我们可以用一个(unordered_)map来统计一个节点子树内权值为的点出现了次。 对于一个点，我们把以该节点为的贡献分成两部分：

  1. 子树内相互贡献(点不同子节点的子树相互贡献)
  2. 子树内对子树外贡献

这样就把这个节点的贡献不重不漏地分成两部分，且都可以根据我们维护的信息快速得出。

1. 子树内相互贡献

对于第一部分，我们暴力合并轻子求解，算法流程如下：

  1. 枚举子树内的信息,如果,将贡献(这里应该先count)计入该点的贡献。
  2. 并入子树内的信息。
  3. 对下一轻子重复1，2.

需要注意的是(注意节点的子树和它的子节点的子树的区别)

  1. 我们不能边计算贡献边把轻子信息并入这个点。因为这样可能导致计算同一子节点的子树内的点的相互贡献，而同一子节点的子树内的点的路径不经过。
  2. 我们不能先把贡献全算一遍，在来加一遍信息。这样会导致只计算了轻子树对重子树的贡献，轻子树之间的贡献没有计算。

这两点对于理解子树内贡献的正确性是非常重要的。

1，2两步的复杂度均为(不考虑map的常数，实际上这里使用unorder_map完全没问题)。由重链剖分的复杂度分析，这部分的复杂度为。

2.子树内对子树外贡献

在计算完第一部分的贡献后，我们合并了这个子树内的信息。于是可以尝试计算子树内对子树外的贡献。(不要推的时候把这部分贡献给搞漏了)
我们可以先预先统计整个树上权值的点数。那么知道了子树内权值为的点数，子树外权值为的点数就相当好得到，为。 一个朴素的计算方法是，遍历这个点上的所有权值,计算出贡献和

。

显然，这个是的，复杂度有问题。 我们要求的贡献是一个类似前缀和的东西(因为大于等于的都被舍去了),考虑尝试使用树状数组维护。 我们考虑拆解贡献的计算式：

我们可以使用两个树状数组分别维护,求解一个点的贡献的复杂度就是求区间和，复杂度是.那么第二部分的总复杂度为 在维护树状数组对前面加入信息的影响。 并入信息的单点修改时间复杂度为,每个点最多加入次那么这部分是时间复杂度为

总结

我们通过分别计算子树内相互贡献、子树内对子树外贡献，总的时间复杂度为