HLD 后在线段树维护已标记 DFS 序最大值，逐链向上找到最近祖先。
OJ: luogu
题目 ID: P4092
难度:提高
标签:重链剖分线段树祖先查询python
日期: 2026-07-17 02:00
题意
标记节点，查询某节点到根路径上最近的已标记祖先。
思路
在 DFS 序位置保存“已标记则为 dfn，否则 0”。查询从节点所在链向上，线段树求 [top[x], x] 的最大 dfn；当前链找到即为最近祖先，否则跳到父链。根初始标记。
Python 知识
- 点标记是幂等的，叶子直接写入 dfn 后向上更新最大值。
- 迭代线段树区间最大值避免频繁递归。
inverse[dfn]把线段树位置恢复为节点编号。
代码
python
import sys
input = sys.stdin.buffer.readline
n, operations = map(int, input().split())
children = [[] for _ in range(n + 1)]
for _ in range(n - 1):
parent, child = map(int, input().split())
children[parent].append(child)
parent = [0] * (n + 1)
depth = [0] * (n + 1)
order = [1]
for node in order:
for child in children[node]:
parent[child] = node
depth[child] = depth[node] + 1
order.append(child)
subtree = [1] * (n + 1)
heavy = [0] * (n + 1)
for node in reversed(order[1:]):
subtree[parent[node]] += subtree[node]
if subtree[node] > subtree[heavy[parent[node]]]:
heavy[parent[node]] = node
top = [0] * (n + 1)
dfn = [0] * (n + 1)
inverse = [0] * (n + 1)
timer = 0
chains = [(1, 1)]
while chains:
node, chain_top = chains.pop()
while node:
top[node] = chain_top
timer += 1
dfn[node] = timer
inverse[timer] = node
for child in children[node]:
if child != heavy[node]:
chains.append((child, child))
node = heavy[node]
size = 1
while size < n:
size <<= 1
segment = [0] * (2 * size)
def mark(node):
position = size + dfn[node] - 1
segment[position] = dfn[node]
position //= 2
while position:
segment[position] = max(segment[position * 2], segment[position * 2 + 1])
position //= 2
def range_max(left, right):
left, right = left - 1 + size, right + size
answer = 0
while left < right:
if left & 1:
answer = max(answer, segment[left])
left += 1
if right & 1:
right -= 1
answer = max(answer, segment[right])
left //= 2
right //= 2
return answer
mark(1)
answers = []
for _ in range(operations):
operation, node = input().split()
node = int(node)
if operation == b'C':
mark(node)
continue
while True:
result = range_max(dfn[top[node]], dfn[node])
if result:
answers.append(str(inverse[result]))
break
node = parent[top[node]]
print("\n".join(answers))原有 C++ 版本仍保留：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-07-17 01:04
* update_at: 2026-07-17 01:04
*/
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
return 0;
}复杂度
每次查询 O(log^2 n)，每次标记 O(log n)，空间 O(n)。
总结
“最近祖先”在同一重链上就是 DFS 序最大的已标记位置。