避难向导

GitHub跳转原题关系图返回列表

树上最远边境城市距离由直径两端决定,再用树链剖分加线段树在路径上二分出第一个安全系数达标的城市。

OJ: roj

题目 ID: 1757

难度:提高+/省选-

标签:树链剖分线段树树的直径数据结构python

创建: 2026-10-07 22:28

更新: 2026-10-07 22:28

形式化题目

给定一棵 nn 个结点的带权树(边权为正整数),结点 11 为首都,任意两点间路径唯一。 度数为 11 的结点称为边境城市。对每个结点 ii 定义

di=max⁡{ dist(i,v)∣v 是边境城市 },Si=((di+a)×b) mod c. d_i = \max\{\,\mathrm{dist}(i, v) \mid v \text{ 是边境城市}\,\}, \qquad S_i = \bigl((d_i + a)\times b\bigr) \bmod c .

给定 mm 个询问 (xi,yi,qi)(x_i, y_i, q_i):在 xix_i 到 yiy_i 的唯一路径上(含两端), 找出离 xix_i 最近的结点 uu,要求 Su≥qiS_u \ge q_i;若不存在这样的结点输出 −1-1。

形式化地说,设路径序列为 x=p0,p1,…,pk=yx = p_0, p_1, \dots, p_k = y(按距 xx 由近到远排列), 要求输出最小的 jj 使得 Spj≥qiS_{p_j} \ge q_i,不存在则输出 −1-1。

数据范围:n≤105n \le 10^5,m≤3×105m \le 3\times 10^5,0<xi,yi≤n0 < x_i, y_i \le n, a,b,c,qi≤106a, b, c, q_i \le 10^6;中间过程需 6464 位整数。

正解

思路

第一步:把 did_i 变成两次 DFS。

直接枚举每个结点到每个边境城市会到 O(n2)O(n^2)。关键结论是树的一个经典性质:

从任意结点出发能到达的最远点,一定是某条直径的端点。

n≥2n \ge 2 时,若直径的某个端点在树中的度数 >1> 1,沿它剩下的那条边再走一步就能得到更长的 路径,矛盾;所以直径两端都是度数为 11 的叶子,也就是边境城市。于是任取结点 11 做一遍 BFS 得到最远点 AA,再从 AA 做一遍得到最远点 BB,此时 A,BA, B 就是一条直径的两端, 且

di=max⁡(dist(i,A),  dist(i,B)). d_i = \max\bigl(\mathrm{dist}(i, A),\; \mathrm{dist}(i, B)\bigr).

两遍 BFS 各 O(n)O(n),SiS_i 也就一起算出来了。

第二步:把询问变成路径上的「第一个达标点」。

询问要求在路径序列 p0,p1,…,pkp_0, p_1, \dots, p_k 上找第一个 S≥qS \ge q 的位置。路径长度可以到 O(n)O(n),询问又有 3×1053\times 10^5 个,必须借用「区间最大值 + 线段树上二分」这套组合。

用树链剖分把树按重链拍到一条数组上,路径 x→yx \to y 被拆成 O(log⁡n)O(\log n) 段连续区间, 且线段树维护区间内 SS 的最大值。判断「这一段里有没有 S≥qS \ge q 的点」只需 O(1)O(1) 比较 根节点的最大值,比 qq 小就整段跳过。

第三步:两半段的扫描方向相反。

路径以 L=lca(x,y)L = \mathrm{lca}(x, y) 为界分成两半,剖分下标沿重链是深度递增的, 所以两半要取的极值位置不一样:

  • x→Lx \to L:从 xx 往上走,每段区间的右端点更靠近 xx,要找最靠右(下标最大) 的达标位置;从 xx 所在的链开始一段段向上,遇到第一个「段内有解」的段就在里面 二分出最右解,直接输出——它就是整条路径上离 xx 最近的答案。
  • L→yL \to y:只有前一半整段无解时才需要。这时离 xx 最近的解等于离 LL 最近的解, 即各段中最靠上的那个。把 y→Ly \to L 的各段按从深到浅收集起来,倒序扫描 (先靠近 LL 的段),在第一个有解的段里二分出最靠左(下标最小)的位置。

两半都无解则输出 −1-1。

正确性。 剖分后每段区间内部的结点在路径上的先后关系与下标大小一致, 段与段之间按扫描顺序单调,所以「先段后段内」的贪心取第一个达标点, 得到的正是路径序列上 jj 最小的那个。

代码

Python 版:

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++ 版(同一算法):

cpp
/**
 * 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 求直径 O(n)O(n);树链剖分 O(n)O(n);建线段树 O(n)O(n)。 每个询问把路径拆成 O(log⁡n)O(\log n) 段,每段一次 O(log⁡n)O(\log n) 的线段树查询, 总时间 O(n+mlog⁡2n)O\bigl(n + m\log^2 n\bigr),n=105,m=3×105n = 10^5, m = 3\times 10^5 时约为 3×105×17×17≈8.7×1073 \times 10^5 \times 17 \times 17 \approx 8.7\times 10^7 次基本操作。
  • 空间:邻接表、剖分数组与线段树均为 O(n)O(n),约 1010 MB 级别,远小于 128 MB 限制。
  • Python 侧:算法与 C++ 完全同阶,但常数大,m=3×105m = 3\times 10^5 的极限点大概率 TLE。按 oj-python-style 的要求,允许 Python TLE,不因此把算法降级成暴力。

总结

  • 树上「最远点」的万能工具:任意点的最远点必是直径端点,于是「到最远叶子的距离」 这类量永远可以退化成两次 BFS,不必真的枚举所有叶子。
  • 把「找第一个达标点」拆成「区间最大值判空 + 树上二分」:先用 O(1)O(1) 的最大值 比较把不含解的段整段跳掉,再只在含解的段里二分,避免了对路径长度做线性扫描。
  • 注意两半段的取极值方向:重链下标随深度递增,向上走要取最右、向下走要取最左, 而且向下那一半的段必须倒序扫描。这是本题最容易写反的地方。
  • 本题数据为自造:素材目录中带有 data.py 生成脚本,data/ 并非官方数据, 题面也是网络重建版本,与官方原题可能存在细节偏差(例如 n=1n = 1 时没有边境城市、 c=0c = 0 时取模无定义等边界)。本地验证结论只能说明「与随仓数据一致」, 不等于官方 AC。