LCA 结合根路径 G 计数，判断一条路径上是否出现指定品种。
OJ: luogu
题目 ID: P5836
难度:普及+/提高-
标签:LCA前缀和树python
日期: 2026-07-17 02:00
题意
判断每条路径上是否有朋友喜欢的牛品种。
思路
根为 1，预处理每个节点到根路径上的 G 数量。路径 a-b 的 G 数量由 prefix[a]+prefix[b]-2*prefix[lca] 加上 LCA 自身修正得到；路径总长度已知，H 数量就是总长度减 G 数量。
Python 知识
- 品种输入保留为 bytes，
b'G'比较无需解码。 array("i")适合深度、父亲和前缀计数。- 多个查询答案用
bytearray直接构造二进制字符串。
代码
python
import sys
from array import array
input = sys.stdin.buffer.readline
n, queries = map(int, input().split())
breeds = b" " + input().strip()
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)
prefix_g = array("i", [0]) * (n + 1)
order = array("i", [1])
depth[1] = 1
prefix_g[1] = breeds[1] == 71
for node in order:
for neighbor in graph[node]:
if neighbor != parent[node]:
parent[neighbor] = node
depth[neighbor] = depth[node] + 1
prefix_g[neighbor] = prefix_g[node] + (breeds[neighbor] == 71)
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]
answer = bytearray()
for _ in range(queries):
x, y, breed = input().split()
x, y = int(x), int(y)
ancestor = lca(x, y)
g_count = prefix_g[x] + prefix_g[y] - 2 * prefix_g[ancestor] + (breeds[ancestor] == 71)
path_length = depth[x] + depth[y] - 2 * depth[ancestor] + 1
answer.append(49 if (g_count if breed == b'G' else path_length - g_count) else 48)
sys.stdout.write(answer.decode())原有 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(n log n)，每次查询 O(log n)，空间 O(n log n)。
总结
路径上某类点的出现性可以先数一种，再用路径长度补出另一种。