还记得 JOISC 赛时写了个 \(O(n\sqrt n\log n)\) 喜提 \(28\) 分，一直以为这个东西只能根号，这下糗大了（
根号直接回滚莫队就行，但是实际上是由 log 做法的！！
考虑离线，然后对于每个点，将这个点到根的路径上的点都染上一个属于这个点的颜色，这样树上每个点所表示的值就是其子树内到目前为止出现的最大的点，那么在最小斯坦纳树上的点就需要满足这个值大于左端点，且在 \([l,r]\) 所有点的 LCA 底下。
上面的过程只需要用满足 \(\geq l\) 的点减去所有点 LCA 的深度即可。染色可以用树剖+BIT 做，对于每条重链维护连续段，暴力就是 \(O(n\log n)\) 段的，于是可以做到 \(O(n\log ^2n)\)，运用多叉树技巧可以做到 \(O(\frac{n\log ^2n}{\log \log n})\)。
标签：6340,log,2n,Tourism,QOJ,根号 From： https://www.cnblogs.com/275307894a/p/17806351.html