5409专题

HDU 5409 CRB and Graph【dfs序+RMQ】

先用trajan缩环变成了一棵树 然后删除了一条边就将树分成了两个部分,一个是删除的那边下面的子树,一个是剩余部分。那么要查询的是两个部分中最大的点的值,和不大于它的最小的点的值。 这样一想就有点像树链剖分啊,树形DP一样求出一颗子树的某个最大值。 又想到是分离出一颗子树,那么就是想到一些dfs序可以对子树进行区间求值。 那么就想到可以预处理出dfs序列,将树的值转化为一个区间值。去掉一颗子