[USACO12DEC]逃跑的BarnRunning Away From…
一个经典问题：
边没有边权，多次询问，查子树中距离x为L的点的个数
n<=1e5，q<=1e5
1.离线，桶维护dep，前后两次，记录桶中的变化（天天爱跑步）
O(n)
边有边权，多次询问，查子树中距离x小于L的点的个数
n<=1e5，q<=1e5
L固定，预处理每个点的答案
1.倍增+差分。枚举每个点考虑贡献，倍增找到链，差分打标记
2.左偏树（线段树合并），不断弹出不合法的。这些点在后面更加不合法
L不固定
子树->dfn序，转化成求一个区间内多少个数小于某个数，主席树
O(nlogn)
边权可以修改？
子树距离根的距离要修改
树状数组套主席树。O(nlog^2n)
[USACO12DEC]逃跑的BarnRunning Away From…
原文：https://www.cnblogs.com/Miracevin/p/10367128.html