题解 P3066 【[USACO12DEC]逃跑的BarnRunning Away From…】

Kelin · 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做的