感觉像大杂烩
各种板子
写了好长
题目链接
题意:
请点链接
…
(题目要求删除区间一个点后某个点的最大深度)
大概解法:
删除区间内dfs序最大或者最小的节点才能使答案最大
先用预处理出每个节点的$2^0,2^1,2^2…$步能到达的节点
还有每个点的深度,dfs序
线段树维护区间dfs序最小值,次小值,次大值,最大值
用线段树询问处要求的区间的最小值,次小值,次大值,最大值
如果要删掉最小值,求出次小值那个点和最大值那个点的最近公共祖先的深度
如果要删除最大值,求出次大值那个点和最小值那个店的最近公共祖先的深度
(因为dfs序相差大的两个点最近公共祖先的深度,才是区间最近公共祖先的最大深度)
比较一下哪个大,输出答案
代码:
1 |
|