自动搬运

查看原文

来自洛谷，原作者为

	Kelin 这个家伙太菜，没什么可以留下的

搬运于2025-08-24 21:44:56，当前版本为作者最后更新于2017-10-01 09:55:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意:给出以1号点为根的一棵有根树,问每个点的子树中与它距离小于等于l的点有多少个

注意输入格式是输入fa[i]&dis[fa[i],i],因为特殊的输入格式,似乎连DFS都不要

法1:如果dep[u]-dep[v]<=len那么u->v路径上的点都要+1,这样我们就可以倍增求出最远的点然后差分就ok了

法2:先把dep,dfs序算出,然后按dep降序排序.对于每个点,需要删除深度相差超过L的点,并加入当前点,在子树中统计答案.(树状数组)

法3:主席树,dep[v]-dep[u]<=L(v∈u)=>dep[v]<=L+dep[u]=>静态区间查询小于某个数的个数 上主席树

法4:树套树,外层区间线段树,内层权值线段树 来做法3的算法

法5:左偏树,先dfs求出dep,再按dfs序倒过来操作

似乎好像,树套树的做法是可以做带修改的,主席树的做法是可以在线给L做的