大融合，但是补充lxl的tj

· · 题解

鲜花

lxl 的题解看起来晦涩难懂，看不懂一点，但是有图。

luogu 只有一篇 lxl 讲的神奇写法，还是看不懂，写太少了。

于是我两篇一起看，，，好耶看懂了！

所以这篇题解就是解释一下 lxl 到底想表示什么个鸟意思。

sol

如图，我们要算边 (4,5) 的答案。

那么不难发现，点集 S_1 = {1,2,3,4}，S_2 = {5,6,7,8 } 。

其中不同集合里各选一个都可以组成一组答案，所以答案即为(siz_1-siz_5)\times siz_5。

所以我们只需维护子树大小了。

那么怎么考虑处理这子树大小呢？

画图一下，看加边会影响到哪些点，令每个点的点权为 siz_i 如果我们加了 (4,5) 进去。

如图，被圈起来的这条链的大小都要 +siz_5，相当于我们每次修改都是把 从这个子树的所有根 1 开始，修改到 修改前不在一棵树上的点 的链给加上子树大小，就如图中的 (1,5) 全加上 siz_5，于是核心思路就弄完了。

讲到这里其实就可以树剖了。

其实弄个 dfn 那树状数组也能轻松做。

具体实现方法就是很树上差分。

把这条链的终点给加上，起点的给减掉，然后查询就从查询链变成了查询子树和，树状数组维护 dfn 上的 (L[i],R[i]) 即可。

于是 O(n \log n) 当场爽撸。

代码不给了。