题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3626
题解：正解没yy出来，想了一个在树形态是随机的情况下的暴力。
我们由dfs序建主席树，每次沿询问的x向上爬，不妨设当前从x爬到了y，那么y的子树中编号属于（l，r）的点的个数-x的子树中编号属于（l，r）的点的个数 *dep[y]就是y对ans的贡献。
查询这一步可以主席树。由于随机数据期望树高是logn的，所以总复杂度是log^2n。。。
当然这都是傻逼了。。。
正解可以戳hzwer
比较神奇的一点就是对于x，如果我们把x到根的路径权值全部+1，那么求y到根的权值和正好计入了dep[lca(x,y)]。所以我们可以离线一个一个插入之后然后查询。
代码：（发现最近知道题目做法之后就不想写代码了QAQ）
原文：http://www.cnblogs.com/zyfzyf/p/4364258.html