G

· · 题解

G

学习_ChiFan_ 的题解。

考虑从小到大枚举 w，顺便加入所有的 v。于是我们直接讨论 u，v 和 w 的位置关系。

如有一个在子树内一个在子树外或在不同的子树内，但是我们发现怎么样都是一个子树或一个子树减掉一个子树或全局减掉一个子树内的 v 给 u 做贡献。

所以我们直接用树状数组维护 dfs 序即可。

code