树上最远边境城市距离由直径两端决定,再用树链剖分加线段树在路径上二分出第一个安全系数达标的城市。
OJ: roj
题目 ID: 1757
难度:提高+/省选-
标签:树链剖分线段树树的直径数据结构python
创建: 2026-10-07 22:28
更新: 2026-10-07 22:28
形式化题目
给定一棵
给定
形式化地说,设路径序列为
数据范围:
正解
思路
第一步:把
直接枚举每个结点到每个边境城市会到
从任意结点出发能到达的最远点,一定是某条直径的端点。
两遍 BFS 各
第二步:把询问变成路径上的「第一个达标点」。
询问要求在路径序列
用树链剖分把树按重链拍到一条数组上,路径
第三步:两半段的扫描方向相反。
路径以
:从 往上走,每段区间的右端点更靠近 ,要找最靠右(下标最大) 的达标位置;从 所在的链开始一段段向上,遇到第一个「段内有解」的段就在里面 二分出最右解,直接输出——它就是整条路径上离 最近的答案。 :只有前一半整段无解时才需要。这时离 最近的解等于离 最近的解, 即各段中最靠上的那个。把 的各段按从深到浅收集起来,倒序扫描 (先靠近 的段),在第一个有解的段里二分出最靠左(下标最小)的位置。
两半都无解则输出
正确性。 剖分后每段区间内部的结点在路径上的先后关系与下标大小一致,
段与段之间按扫描顺序单调,所以「先段后段内」的贪心取第一个达标点,
得到的正是路径序列上
代码
Python 版:
#!/usr/bin/env python3
# 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-10-07 22:28
# update_at: 2026-10-07 22:28
import sys
from collections.abc import Iterator
NONE = -1 # 线段树查询的哨兵:该区间里没有任何安全系数达标的城市
# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Adj = list[list[tuple[int, int]]] # 邻接表:点 -> [(邻点, 边权)]
type Tree = list[int] # 迭代式线段树,下标 1 起,存区间最大安全系数
type Hld = tuple[list[int], list[int], list[int], list[int], list[int]]
# Hld = (par, dep, head, pos, node_at):父结点 / 深度 / 重链链头 / 剖分下标 / 下标对应点
type Seg = tuple[Tree, int] # (线段树, 叶子偏移 size)
def tree_bfs(adj: Adj, root: int) -> tuple[list[int], list[int], list[int], list[int]]:
"""从 root 做 BFS,返回(访问序、父结点、深度、带权距离)。"""
n = len(adj) - 1
par = [0] * (n + 1)
dep = [0] * (n + 1)
dist = [0] * (n + 1)
order = [root]
for u in order: # 边遍历边追加:BFS 序里父结点一定先于子结点出现
for v, w in adj[u]:
if v != par[u]:
par[v] = u
dep[v] = dep[u] + 1
dist[v] = dist[u] + w
order.append(v)
return order, par, dep, dist
def farthest_node(adj: Adj, start: int) -> tuple[int, list[int]]:
"""返回离 start 最远的点编号,以及各点到 start 的距离。"""
_order, _par, _dep, dist = tree_bfs(adj, start)
best = start
for i in range(1, len(dist)):
if dist[i] > dist[best]:
best = i
return best, dist
def safety_values(adj: Adj, a: int, b: int, c: int) -> list[int]:
"""每个城市的安全系数 S_i = ((d_i + a) * b) mod c。
d_i 是「到最远边境城市的距离」。树里任意点的最远点必是直径端点,
而直径两端都是叶子(度 1),也就是边境城市,所以两遍 BFS 定出直径两端 A、B 后
d_i = max(dist(i, A), dist(i, B));n = 1 时没有边境城市,两个距离都是 0。
"""
end_a, _ = farthest_node(adj, 1) # 任取一点求最远点 A
end_b, dist_a = farthest_node(adj, end_a) # A 的最远点就是直径另一端 B
_, dist_b = farthest_node(adj, end_b)
return [0] + [((max(dist_a[i], dist_b[i]) + a) * b) % c for i in range(1, len(adj))]
def heavy_light(adj: Adj) -> Hld:
"""树链剖分:重链在 pos 上占一段连续下标,且下标随深度递增。"""
n = len(adj) - 1
order, par, dep, _dist = tree_bfs(adj, 1)
# 子树大小与重儿子:逆 BFS 序自底向上合并
sub = [1] * (n + 1)
heavy = [0] * (n + 1)
for u in reversed(order[1:]):
p = par[u]
sub[p] += sub[u]
if heavy[p] == 0 or sub[u] > sub[heavy[p]]:
heavy[p] = u
# 每个链头带着它的重链一路往下占下标
head = [0] * (n + 1)
pos = [0] * (n + 1)
node_at = [0] * n
cur = 0
for u in order:
if u == 1 or heavy[par[u]] != u: # u 是链头(根,或不是父结点的重儿子)
v = u
while v:
head[v] = u
pos[v] = cur
node_at[cur] = v
cur += 1
v = heavy[v]
return par, dep, head, pos, node_at
def lca(u: int, v: int, hld: Hld) -> int:
"""最近公共祖先:谁所在重链的链头更深就先跳谁。"""
par, dep, head = hld[0], hld[1], hld[2]
while head[u] != head[v]:
if dep[head[u]] < dep[head[v]]:
u, v = v, u
u = par[head[u]]
return u if dep[u] < dep[v] else v
def build_seg(values: list[int]) -> Seg:
"""按剖分下标顺序建迭代式线段树,返回 (树, 叶子偏移)。"""
size = 1
while size < len(values):
size <<= 1
tree = [0] * (2 * size)
tree[size:size + len(values)] = values
for i in range(size - 1, 0, -1):
tree[i] = max(tree[2 * i], tree[2 * i + 1])
return tree, size
def seg_nodes(lo: int, hi: int, size: int) -> tuple[list[int], list[int]]:
"""把区间 [lo, hi] 拆成线段树的标准结点,返回(左半从左到右、右半从右到左)。
左右两半拼起来是 [左半] + 反转(右半),即从左到右的覆盖顺序。
"""
lo += size
hi += size + 1
left: list[int] = []
right: list[int] = []
while lo < hi:
if lo & 1:
left.append(lo)
lo += 1
if hi & 1:
hi -= 1
right.append(hi)
lo >>= 1
hi >>= 1
return left, right
def rightmost(tree: Tree, size: int, lo: int, hi: int, q: int) -> int:
"""[lo, hi] 内下标最大且值 >= q 的叶子位置,没有则 NONE。"""
left, right = seg_nodes(lo, hi, size)
for nd in right + left[::-1]: # 从右往左扫标准结点,首个含解的结点里再往右沉
if tree[nd] >= q:
while nd < size:
nd = 2 * nd + 1 if tree[2 * nd + 1] >= q else 2 * nd
return nd - size
return NONE
def leftmost(tree: Tree, size: int, lo: int, hi: int, q: int) -> int:
"""[lo, hi] 内下标最小且值 >= q 的叶子位置,没有则 NONE。"""
left, right = seg_nodes(lo, hi, size)
for nd in left + right[::-1]: # 从左往右扫标准结点,首个含解的结点里再往左沉
if tree[nd] >= q:
while nd < size:
nd = 2 * nd if tree[2 * nd] >= q else 2 * nd + 1
return nd - size
return NONE
def first_on_path(x: int, y: int, q: int, hld: Hld, seg: Seg) -> int:
"""x -> y 路径上离 x 最近且安全系数 >= q 的城市编号,不存在返回 -1。
路径以 lca 为界分两半:x 到 lca 这一半要从 x 往上走,取最靠右(下标最大)的解;
只有它整段无解时才看 lca 到 y 那一半,此时离 x 最近等于离 lca 最近,
于是把各段按从深到浅收好、倒序扫描,段内取最靠左的解。
"""
par, dep, head, pos, node_at = hld
tree, size = seg
top = lca(x, y, hld)
u = x
while head[u] != head[top]:
idx = rightmost(tree, size, pos[head[u]], pos[u], q)
if idx != NONE:
return node_at[idx]
u = par[head[u]]
idx = rightmost(tree, size, pos[top], pos[u], q)
if idx != NONE:
return node_at[idx]
down: list[tuple[int, int]] = []
v = y
while head[v] != head[top]:
down.append((pos[head[v]], pos[v]))
v = par[head[v]]
if pos[v] > pos[top]: # 同一条重链上的最后一小段,去掉 lca 自己
down.append((pos[top] + 1, pos[v]))
for lo, hi in reversed(down):
idx = leftmost(tree, size, lo, hi, q)
if idx != NONE:
return node_at[idx]
return -1
def solve() -> None:
data: Iterator[int] = iter(map(int, sys.stdin.buffer.read().split()))
n, m = next(data), next(data)
a, b, c = next(data), next(data), next(data)
adj: Adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
u, v, w = next(data), next(data), next(data)
adj[u].append((v, w))
adj[v].append((u, w))
safety = safety_values(adj, a, b, c)
hld = heavy_light(adj)
node_at = hld[4]
seg = build_seg([safety[node_at[i]] for i in range(n)])
out: list[int] = []
for _ in range(m):
x, y, q = next(data), next(data), next(data)
out.append(first_on_path(x, y, q, hld, seg))
sys.stdout.write('\n'.join(map(str, out)) + '\n')
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* 1757 避难向导
*
* 题意:给定一棵 n 个点的带权树(1 号点为首都)。只与一条公路相连的城市称为边境城市。
* 每个城市的封闭系数 d_i = 离 i 最远的边境城市到 i 的距离;
* 安全系数 S_i = (d_i + a) * b mod c。
* m 次询问 (x, y, q):在 x 到 y 的必经之路(即树上唯一路径)上,找离 x 最近的
* 且 S >= q 的城市编号(包含 x 和 y),不存在则输出 -1。
*
* 关键结论:
* 1. 树中任意点的最远点一定是某条直径的端点;而 n >= 2 时直径端点必为叶子(度 1),
* 也就是边境城市。因此 d_i = max(dist(i, A), dist(i, B)),A、B 为一条直径的两端。
* 求直径只需从任意点做两遍 DFS:先求最远点 A,再从 A 求最远点 B。
* 2. 询问等价于「在 x -> y 的路径序列上找第一个 S >= q 的位置」。
* 用树链剖分把路径拆成 O(log n) 段连续区间,线段树上维护区间 S 的最大值;
* x -> lca 部分是自 x 向 lca 走,需要区间内「最靠右」的满足点;
* lca -> y 部分需要「最靠上」的满足点,倒序扫描各段即可。
*
* 复杂度:O((n + m) log^2 n) 时间,O(n) 空间。
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005; // 城市数上限
const int MAXM = 300005; // 询问数上限
int n, m; // 城市数、询问数
ll A, B, C; // 幸运数字 a, b, c
struct Edge { int to; ll w; };
vector<Edge> g[MAXN]; // 邻接表
int par[MAXN]; // 父结点
int dep[MAXN]; // 深度(边数)
int sz[MAXN]; // 子树大小
int heavy[MAXN]; // 重儿子
int head[MAXN]; // 所在重链的链头
int pos[MAXN]; // 树链剖分后在线段树中的下标
int nodeAt[MAXN]; // 下标 -> 原编号
ll distRoot[MAXN]; // 到 1 号点的距离
ll S[MAXN]; // 安全系数
ll segMax[4 * MAXN]; // 线段树:区间 S 最大值
/** 从 root 出发做 BFS,得到 par / dep / distRoot / 访问顺序 order */
void bfsOrder(int root, int *order) {
int qh = 0, qt = 0;
static int que[MAXN];
par[root] = 0; dep[root] = 0; distRoot[root] = 0;
que[qt++] = root;
while (qh < qt) {
int u = que[qh++];
order[qh - 1] = u; // 出队顺序即 BFS 序
for (size_t i = 0; i < g[u].size(); i++) {
int v = g[u][i].to;
if (v == par[u]) continue;
par[v] = u;
dep[v] = dep[u] + 1;
distRoot[v] = distRoot[u] + g[u][i].w;
que[qt++] = v;
}
}
}
/** 求距离 start 最远的结点编号(树的直径端点) */
int farthest(int start) {
static int order[MAXN];
bfsOrder(start, order);
int best = start;
for (int i = 1; i <= n; i++)
if (distRoot[i] > distRoot[best]) best = i;
return best;
}
/** 树链剖分:求 sz / heavy / head / pos / nodeAt */
void buildHLD() {
static int order[MAXN];
bfsOrder(1, order);
// 逆 BFS 序统计子树大小与重儿子
for (int i = 1; i <= n; i++) { sz[i] = 1; heavy[i] = 0; }
for (int i = n - 1; i >= 1; i--) { // order[0..n-1],跳过根
int u = order[i];
sz[par[u]] += sz[u];
if (heavy[par[u]] == 0 || sz[u] > sz[heavy[par[u]]]) heavy[par[u]] = u;
}
// 沿重链分配连续下标
int cur = 0;
for (int i = 0; i < n; i++) {
int u = order[i];
if (u == 1 || heavy[par[u]] != u) { // 链头
for (int v = u; v != 0; v = heavy[v]) {
head[v] = u;
pos[v] = cur;
nodeAt[cur] = v;
cur++;
}
}
}
}
void build(int node, int l, int r) {
if (l == r) { segMax[node] = S[nodeAt[l]]; return; }
int mid = (l + r) >> 1;
build(node << 1, l, mid);
build(node << 1 | 1, mid + 1, r);
segMax[node] = max(segMax[node << 1], segMax[node << 1 | 1]);
}
/** 区间 [l, r] 中最靠右(下标最大)的 S >= q 的位置,不存在返回 -1 */
int queryRight(int node, int nl, int nr, int l, int r, ll q) {
if (r < nl || nr < l || segMax[node] < q) return -1;
if (nl == nr) return nl;
int mid = (nl + nr) >> 1;
int res = queryRight(node << 1 | 1, mid + 1, nr, l, r, q); // 先右后左
if (res != -1) return res;
return queryRight(node << 1, nl, mid, l, r, q);
}
/** 区间 [l, r] 中最靠左(下标最小)的 S >= q 的位置,不存在返回 -1 */
int queryLeft(int node, int nl, int nr, int l, int r, ll q) {
if (r < nl || nr < l || segMax[node] < q) return -1;
if (nl == nr) return nl;
int mid = (nl + nr) >> 1;
int res = queryLeft(node << 1, nl, mid, l, r, q); // 先左后右
if (res != -1) return res;
return queryLeft(node << 1 | 1, mid + 1, nr, l, r, q);
}
int lca(int u, int v) {
while (head[u] != head[v]) {
if (dep[head[u]] < dep[head[v]]) swap(u, v);
u = par[head[u]];
}
return dep[u] < dep[v] ? u : v;
}
/** 询问:x -> y 路径上离 x 最近的 S >= q 的城市编号 */
int solve(int x, int y, ll q) {
int l = lca(x, y);
int u = x;
// 第一段:从 x 向上走到 l,越靠 x 下标越大,取最右
while (head[u] != head[l]) {
int r = queryRight(1, 0, n - 1, pos[head[u]], pos[u], q);
if (r != -1) return nodeAt[r];
u = par[head[u]];
}
int r1 = queryRight(1, 0, n - 1, pos[l], pos[u], q);
if (r1 != -1) return nodeAt[r1];
// 第二段:从 l 向下走到 y(不含 l),越靠 l 下标越小,需要最靠上的一段
static int segs[64][2];
int cnt = 0;
int v = y;
while (head[v] != head[l]) {
segs[cnt][0] = pos[head[v]];
segs[cnt][1] = pos[v];
cnt++;
v = par[head[v]];
}
if (pos[v] > pos[l]) {
segs[cnt][0] = pos[l] + 1;
segs[cnt][1] = pos[v];
cnt++;
}
for (int i = cnt - 1; i >= 0; i--) { // 倒序:先靠近 l 的段
int r = queryLeft(1, 0, n - 1, segs[i][0], segs[i][1], q);
if (r != -1) return nodeAt[r];
}
return -1;
}
int main() {
scanf("%d %d %lld %lld %lld", &n, &m, &A, &B, &C);
for (int i = 1; i < n; i++) {
int u, v; ll w;
scanf("%d %d %lld", &u, &v, &w);
g[u].push_back((Edge){v, w});
g[v].push_back((Edge){u, w});
}
// 1. 求直径两端 A、B,得到每个点的封闭系数
static ll distA[MAXN];
int p1 = farthest(1);
int p2 = farthest(p1);
for (int i = 1; i <= n; i++) distA[i] = distRoot[i]; // 距 p1
farthest(p2); // 现在 distRoot 为距 p2
for (int i = 1; i <= n; i++) {
ll d = max(distA[i], distRoot[i]); // n = 1 时两者均为 0
S[i] = (d % C + A % C) % C * (B % C) % C; // (d + a) * b mod c
}
// 2. 树链剖分 + 线段树
buildHLD();
build(1, 0, n - 1);
// 3. 回答询问
for (int i = 0; i < m; i++) {
int x, y; ll q;
scanf("%d %d %lld", &x, &y, &q);
printf("%d\n", solve(x, y, q));
}
return 0;
}复杂度
- 时间:两遍 BFS 求直径
;树链剖分 ;建线段树 。 每个询问把路径拆成 段,每段一次 的线段树查询, 总时间 , 时约为 次基本操作。 - 空间:邻接表、剖分数组与线段树均为
,约 MB 级别,远小于 128 MB 限制。 - Python 侧:算法与 C++ 完全同阶,但常数大,
的极限点大概率 TLE。按 oj-python-style的要求,允许 Python TLE,不因此把算法降级成暴力。
总结
- 树上「最远点」的万能工具:任意点的最远点必是直径端点,于是「到最远叶子的距离」 这类量永远可以退化成两次 BFS,不必真的枚举所有叶子。
- 把「找第一个达标点」拆成「区间最大值判空 + 树上二分」:先用
的最大值 比较把不含解的段整段跳掉,再只在含解的段里二分,避免了对路径长度做线性扫描。 - 注意两半段的取极值方向:重链下标随深度递增,向上走要取最右、向下走要取最左, 而且向下那一半的段必须倒序扫描。这是本题最容易写反的地方。
- 本题数据为自造:素材目录中带有
data.py生成脚本,data/并非官方数据, 题面也是网络重建版本,与官方原题可能存在细节偏差(例如时没有边境城市、 时取模无定义等边界)。本地验证结论只能说明「与随仓数据一致」, 不等于官方 AC。
【数据规模及提示】
对于100%的数据,