G题最简单做法题解。看没人写dsu/线段树合并的题解来写一个，出题人只提了一嘴这个做法没有细说，这感觉也算经典线段树合并dp/计数的模式了。看出题人建立虚树的做法思路是通过三个点中的来互相计数的，这里我们通过找来计数其实更简单，问题转化为对于一个点，考虑有几对相同的对路径经过它，且。我用的线段树合并来解决这个问题，具体来说，合并到某个点的时候，对于子树内相互匹配的点，我们可以边合并边计数，我们在的时候先记一下，若在线段树叶子节点发生合并，且合并位置的，则此时会发生贡献，为（假设合并的节点为，且这种分别有个）。对于子树外和子树内匹配的点，我们在子树合并完后统计，具体而言，我们这时候其实可以知道每...