用 LCA 和树上点差分统计所有路径经过每个牧场的次数。
OJ: luogu
题目 ID: P3128
难度:普及+/提高-
标签:LCA树上差分树python
日期: 2026-07-17 02:00
题意
给出许多树上路径，求经过路径最多的节点流量。
思路
对路径 u-v、g=lca(u,v) 做点差分：diff[u] += 1、diff[v] += 1、diff[g] -= 1、diff[parent[g]] -= 1。最后按 DFS 逆序把子树差分累加到父亲，得到每个节点经过的路径数。
Python 知识
- 倍增表用
array("i")，差分用普通整数列表便于累加。 reversed(order)是树上后序汇总的简洁写法。- LCA 函数同时服务路径差分和距离层级逻辑。
代码
python
import sys
from array import array
input = sys.stdin.buffer.readline
n, path_count = 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 = array("i", [0]) * (n + 1)
depth = array("i", [0]) * (n + 1)
depth[1] = 1
order = array("i", [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)
ancestors = [parent]
for _ in range(1, n.bit_length()):
previous = ancestors[-1]
ancestors.append(array("i", (previous[previous[node]] for node in range(n + 1))))
def lca(x, y):
if depth[x] < depth[y]:
x, y = y, x
difference = depth[x] - depth[y]
bit = 0
while difference:
if difference & 1:
x = ancestors[bit][x]
difference >>= 1
bit += 1
if x == y:
return x
for level in range(len(ancestors) - 1, -1, -1):
if ancestors[level][x] != ancestors[level][y]:
x = ancestors[level][x]
y = ancestors[level][y]
return parent[x]
difference = [0] * (n + 1)
for _ in range(path_count):
start, end = map(int, input().split())
ancestor = lca(start, end)
difference[start] += 1
difference[end] += 1
difference[ancestor] -= 1
difference[parent[ancestor]] -= 1
answer = 0
for node in reversed(order):
answer = max(answer, difference[node])
difference[parent[node]] += difference[node]
print(answer)原有 C++ 版本仍保留：
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50005;
const int LOG = 16;
int n, k;
int head[MAXN], to[MAXN * 2], nxt[MAXN * 2], edge_cnt;
int depth_node[MAXN];
int up[MAXN][LOG + 1]; // up[x][j] 表示 x 的 2^j 级祖先。
long long diff_count[MAXN]; // 树上点差分数组，最后自底向上汇总成每个点的流量。
long long answer;
void add_edge(int u, int v) {
edge_cnt++;
to[edge_cnt] = v;
nxt[edge_cnt] = head[u];
head[u] = edge_cnt;
}
void read_input() {
cin >> n >> k;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
add_edge(u, v);
add_edge(v, u);
}
}
void build_lca() {
queue<int> que;
que.push(1);
depth_node[1] = 1;
// BFS 建树，避免深递归在链形树上爆栈。
while (!que.empty()) {
int u = que.front();
que.pop();
for (int j = 1; j <= LOG; j++) {
up[u][j] = up[up[u][j - 1]][j - 1];
}
for (int i = head[u]; i != 0; i = nxt[i]) {
int v = to[i];
if (v == up[u][0]) {
continue;
}
up[v][0] = u;
depth_node[v] = depth_node[u] + 1;
que.push(v);
}
}
}
int lca(int x, int y) {
if (depth_node[x] < depth_node[y]) {
swap(x, y);
}
int diff = depth_node[x] - depth_node[y];
for (int j = LOG; j >= 0; j--) {
if ((diff & (1 << j)) != 0) {
x = up[x][j];
}
}
if (x == y) {
return x;
}
for (int j = LOG; j >= 0; j--) {
if (up[x][j] != up[y][j]) {
x = up[x][j];
y = up[y][j];
}
}
return up[x][0];
}
void collect_answer() {
vector<int> order;
queue<int> que;
que.push(1);
while (!que.empty()) {
int u = que.front();
que.pop();
order.push_back(u);
for (int i = head[u]; i != 0; i = nxt[i]) {
int v = to[i];
if (v == up[u][0]) {
continue;
}
que.push(v);
}
}
for (int i = (int)order.size() - 1; i >= 0; i--) {
int u = order[i];
answer = max(answer, diff_count[u]);
if (up[u][0] != 0) {
diff_count[up[u][0]] += diff_count[u];
}
}
}
void solve() {
build_lca();
for (int i = 1; i <= k; i++) {
int u, v;
cin >> u >> v;
int g = lca(u, v);
// 点差分：让路径 u -> v 上所有点最终都加 1。
// u、v 两端各加一；lca 和 lca 的父亲负责截断向根方向的多余贡献。
diff_count[u]++;
diff_count[v]++;
diff_count[g]--;
if (up[g][0] != 0) {
diff_count[up[g][0]]--;
}
}
collect_answer();
cout << answer << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
solve();
return 0;
}复杂度
预处理 O(n log n)，每条路径 O(log n)，总空间 O(n log n)。
总结
树上路径“经过次数”可以把逐条路径标记变成端点差分和一次后序累加。