我要加训 ds。

Ynoi2011 成都七中

标算其实是点分树上直接做，但是我并没有很懂。

先只考虑 \(l\) 的限制，将树边边权设为 \(min(u,v)\)，直接跑 Kruskal 重构树，于是 \(x\) 所在连通块就是重构树上的一个子树（子树根可以通过倍增跳上去找到）。

\(r\) 限制同理，于是所求即为同个点集构成的两棵树的子树的交中颜色数。离线下来，对第一个树跑 dsu on tree，对第二个树只需要维护单点加入/删除和子树查询颜色数，直接拍平到 dfn 序列上是双 \(\log\) 的，但是考虑子树查询所以做一步类似树上差分的事情，加入时在和同颜色前驱、后继的 lca 上贡献减一，在这两个 lca 的 lca 上贡献加一即可，于是只需要一个 bit 即可。算上第一个树上 dsu on tree 的复杂度，总复杂度为 \(O(n\log^n+m\log n)\)，可以通过。