竞选弱智吧吧主的G题 $n\sqrt{nlog_2n}$ 做法

竞选弱智吧吧主的G题 做法。

将找到符合条件的三元组对拆成两步：

1. 找到权值相同的点对；
2. 统计权值相同点对的路径上，有多少个点的权值大于该点对。

找同色点对可以按照如下方法根号分治——统计每种权值的出现次数：

• 如果某种权值的出现次数小于等于 ，我们暴力枚举这种权值的所有点对，用一些算法在 的时间内查询点对的路径上有多少权值大于点对的点。按照这种方法，我们至多枚举到 个点对，这部分的总复杂度是 。
• 如果某种权值的出现次数大于 ，我们专门针对这种权值搜索一遍整棵树，统计该权值的所有点对的总答案，复杂度可做到 。出现次数大于 的权值不可能超过 种，这部分的总复杂度就是 。

当 时，两部分的复杂度均为 。

对于出现次数小于等于 的权值如何统计：想象一开始所有点都是白色，按照从大到小的顺序枚举这些权值，将枚举到的点染成黑色，问题就变成：“查询路径上权值大于点对的点的数目”这一问题就变成“查询路径上黑色节点的数目”。用树状数组维护树上每个节点到根节点路径上的黑色节点数目，将一个节点染黑就是使一个子树（即DFS序上的一个区间）内的所有节点到根节点路径上的黑节点数目+1；点对路径上的黑色节点数目就是这两个点到根节点路径上的黑色节点数目之和，减去它们的LCA到根节点路径上的黑色节点数目之和。

对于出现次数大于 的权值如何统计：先搜一遍统计每个子树内有多少个节点的权值是我们当前正在统计的权值，然后枚举每个大于统计权值的点，看以它为根时每个子树内分别有几个节点，乘一下。

复杂度很垃圾，需要多优化卡常，慎写。