重链剖分拆树上路径，Fenwick 差分支持道路覆盖加法和单边查询。
OJ: luogu
题目 ID: P3038
难度:普及+/提高-
标签:重链剖分树状数组树上差分python
日期: 2026-07-17 02:00
题意
给树上路径经过的每条道路加一，查询某条道路被覆盖次数。
思路
把每条父子边绑定到较深端点。HLD 将路径拆段；更新时不包含 LCA 对应点，只给子树方向的 DFS 区间加一。Fenwick 维护差分，单点前缀和就是该道路的覆盖次数。
Python 知识
byte操作标记直接比较b'P'/b'Q'，省去解码。add(right + 1, -value)是区间差分的标准端点写法。- HLD 循环中总是把深链端抬高，代码无需递归。
代码
python
import sys
input = sys.stdin.buffer.readline
n, operations = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
u, v = map(int, input().split())
graph[u].append(v)
graph[v].append(u)
parent = [0] * (n + 1)
depth = [0] * (n + 1)
order = [1]
for node in order:
for neighbor in graph[node]:
if neighbor != parent[node]:
parent[neighbor] = node
depth[neighbor] = depth[node] + 1
order.append(neighbor)
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)
timer = 0
chains = [(1, 1)]
while chains:
node, chain_top = chains.pop()
while node:
top[node] = chain_top
timer += 1
dfn[node] = timer
for neighbor in graph[node]:
if neighbor != parent[node] and neighbor != heavy[node]:
chains.append((neighbor, neighbor))
node = heavy[node]
bit = [0] * (n + 2)
def add(index, value):
while index <= n:
bit[index] += value
index += index & -index
def prefix(index):
result = 0
while index:
result += bit[index]
index -= index & -index
return result
def range_add(left, right, value):
add(left, value)
add(right + 1, -value)
def path_update(x, y):
while top[x] != top[y]:
if depth[top[x]] < depth[top[y]]:
x, y = y, x
range_add(dfn[top[x]], dfn[x], 1)
x = parent[top[x]]
if depth[x] > depth[y]:
x, y = y, x
if x != y:
range_add(dfn[x] + 1, dfn[y], 1)
def edge_query(x, y):
child = x if depth[x] > depth[y] else y
return prefix(dfn[child])
answers = []
for _ in range(operations):
operation, x, y = input().split()
x, y = int(x), int(y)
if operation == b'P':
path_update(x, y)
else:
answers.append(str(edge_query(x, y)))
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(n)。
总结
道路问题先转成“子节点代表父边”，再复用点路径的 HLD 拆分。