竞选弱智吧吧主的G题 做法。 将找到符合条件的三元组对拆成两步： 找到权值相同的点对； 统计权值相同点对的路径上，有多少个点的权值大于该点对。 找同色点对可以按照如下方法根号分治——统计每种权值的出现次数： 如果某种权值的出现次数小于等于 ，我们暴力枚举这种权值的所有点对，用一些算法在 的时间内查询点对的路径上有多少权值大于点对的点。按照这种方法，我们至多枚举到 个点对，这部分的总复杂度是 。 如果某种权值的出现次数大于 ，我们专门针对这种权值搜索一遍整棵树，统计该权值的所有点对的总答案，复杂度可做到 。出现次数大于 的权值不可能超过 种，这部分的总复杂度就是 。 ...

😂