[NOIP2024] 树上查询

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

把连续编号区间的 LCA 深度转成相邻 LCA 深度数组的区间最小值，再离线二分答案。

OJ: luogu

题目 ID: P11364

难度:省选/NOI-

标签:树形结构LCA二分线段树离线

日期: 2026-06-22 19:30

题意

给定一棵以 1 为根的树，节点编号为 1..n。节点深度定义为从根到该节点路径上的节点数量。

LCA*(l, r) 表示编号在 [l, r] 内所有节点的最近公共祖先。每次询问给出 l, r, k，要在 [l, r] 的所有长度至少为 k 的连续编号子区间 [l', r'] 中，求 dep(LCA*(l', r')) 的最大值。

如果 k = 1，可以只选一个节点，答案就是编号区间 [l, r] 内节点深度的最大值。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 55;

int n, q;
vector<int> tree[MAXN];
int parent_node[MAXN], depth_node[MAXN];

void dfs_build(int u, int fa) {
    parent_node[u] = fa;
    depth_node[u] = (fa == 0 ? 1 : depth_node[fa] + 1);
    for (int i = 0; i < (int)tree[u].size(); i++) {
        int v = tree[u][i];
        if (v == fa) {
            continue;
        }
        dfs_build(v, u);
    }
}

int lca_pair(int u, int v) {
    while (depth_node[u] > depth_node[v]) {
        u = parent_node[u];
    }
    while (depth_node[v] > depth_node[u]) {
        v = parent_node[v];
    }
    while (u != v) {
        u = parent_node[u];
        v = parent_node[v];
    }
    return u;
}

int lca_interval(int l, int r) {
    int cur = l;
    for (int i = l + 1; i <= r; i++) {
        cur = lca_pair(cur, i);
    }
    return cur;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    dfs_build(1, 0);

    cin >> q;
    while (q--) {
        int l, r, k;
        cin >> l >> r >> k;

        int ans = 0;
        for (int left = l; left <= r; left++) {
            for (int right = left + k - 1; right <= r; right++) {
                int x = lca_interval(left, right);
                ans = max(ans, depth_node[x]);
            }
        }
        cout << ans << '\n';
    }

    return 0;
}

暴力做法会枚举每个询问里的所有连续子区间，再逐个求这些节点的 LCA。这个思路非常直观，但一个询问就可能有二次方个子区间，无法处理 5 * 10^5 的数据范围。

关键是把“连续编号节点的 LCA”变成一个数组问题。定义：

text

1b[i] = dep(lca(i, i + 1))  (1 <= i < n)

对于长度大于 1 的连续编号区间 [L, R]，有：

text

1dep(LCA*(L, R)) = min(b[L], b[L + 1], ..., b[R - 1])

这张表展示节点区间和 b 数组区间之间的对应关系：

节点区间	对应的 `b` 数组位置	LCA 深度
`[L, L]`	无	`dep[L]`
`[L, L + 1]`	`b[L]`	`b[L]`
`[L, R]`	`b[L..R-1]`	`min(b[L..R-1])`

表里最重要的是第三行：长度大于 1 的节点区间不再直接看所有节点，而是看相邻编号 LCA 深度数组的一段最小值。相邻位置能串起整个连续编号区间，所以只要每一对相邻节点在某个深度处仍有共同祖先，整段节点也在这个深度处有共同祖先。

于是当 k >= 2 时，询问 [l, r, k] 等价于：

text

1
2在 b[l..r-1] 中找一个长度至少为 k-1 的连续子段，
最大化这个子段的最小值。

对答案深度 x 做判定：把所有满足 b[i] >= x 的位置激活。若 [l, r-1] 内存在连续至少 k-1 个激活位置，就说明可以选出一个长度至少为 k 的节点区间，其 LCA 深度至少为 x。

这个判定对 x 单调，所以可以二分答案。为了同时处理所有询问，代码使用并行二分：每一轮把询问按当前二分中点分桶，然后按阈值从大到小扫描并激活位置。

线段树维护每个区间的四个量：

len：区间长度；
pref：最长激活前缀；
suf：最长激活后缀；
best：区间内最长连续激活段。

合并两个线段树节点时，跨过中点的连续激活段长度是左儿子的 suf + 右儿子的 pref。查询 [l, r-1] 后，如果 best >= k-1，当前二分值可行。

k = 1 的询问单独处理：预处理节点深度的 ST 表，直接查询编号区间 [l, r] 内最大深度。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500005;
const int LOG = 20;

struct Edge {
    int to;
    int next;
};

struct SegNode {
    int len;
    int pref;
    int suf;
    int best;
};

struct Query {
    int left;
    int right;
    int need;
    int id;
};

int n, q;
int head[MAXN], edge_cnt;
Edge edges[MAXN * 2];
int depth_node[MAXN];
int up[LOG][MAXN];
int adjacent_depth[MAXN];
int depth_log[MAXN];
int depth_st[LOG][MAXN];
int answer[MAXN];

vector<int> values;
int value_id[MAXN];
int position_order[MAXN];
vector<Query> queries;

SegNode seg[MAXN * 4];
int low_bound_idx[MAXN], high_bound_idx[MAXN], answer_idx[MAXN];
int bucket_head[MAXN], bucket_next[MAXN];
vector<int> used_bucket;

void add_edge(int u, int v) {
    edge_cnt++;
    edges[edge_cnt].to = v;
    edges[edge_cnt].next = head[u];
    head[u] = edge_cnt;
}

SegNode merge_node(SegNode a, SegNode b) {
    SegNode c;
    c.len = a.len + b.len;
    c.pref = a.pref;
    if (a.pref == a.len) {
        c.pref = a.len + b.pref;
    }
    c.suf = b.suf;
    if (b.suf == b.len) {
        c.suf = b.len + a.suf;
    }
    c.best = max(max(a.best, b.best), a.suf + b.pref);
    return c;
}

void build_seg(int p, int l, int r) {
    seg[p].len = r - l + 1;
    seg[p].pref = seg[p].suf = seg[p].best = 0;
    if (l == r) {
        return;
    }
    int mid = (l + r) >> 1;
    build_seg(p << 1, l, mid);
    build_seg(p << 1 | 1, mid + 1, r);
}

void reset_seg(int p, int l, int r) {
    seg[p].pref = seg[p].suf = seg[p].best = 0;
    if (l == r) {
        return;
    }
    int mid = (l + r) >> 1;
    reset_seg(p << 1, l, mid);
    reset_seg(p << 1 | 1, mid + 1, r);
}

void activate_position(int p, int l, int r, int pos) {
    if (l == r) {
        seg[p].pref = seg[p].suf = seg[p].best = 1;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) {
        activate_position(p << 1, l, mid, pos);
    } else {
        activate_position(p << 1 | 1, mid + 1, r, pos);
    }
    seg[p] = merge_node(seg[p << 1], seg[p << 1 | 1]);
}

SegNode query_seg(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return seg[p];
    }
    int mid = (l + r) >> 1;
    if (qr <= mid) {
        return query_seg(p << 1, l, mid, ql, qr);
    }
    if (ql > mid) {
        return query_seg(p << 1 | 1, mid + 1, r, ql, qr);
    }
    SegNode left_node = query_seg(p << 1, l, mid, ql, qr);
    SegNode right_node = query_seg(p << 1 | 1, mid + 1, r, ql, qr);
    return merge_node(left_node, right_node);
}

void build_lca() {
    vector<int> order;
    order.push_back(1);
    up[0][1] = 0;
    depth_node[1] = 1;

    for (int i = 0; i < (int)order.size(); i++) {
        int u = order[i];
        for (int e = head[u]; e != 0; e = edges[e].next) {
            int v = edges[e].to;
            if (v == up[0][u]) {
                continue;
            }
            up[0][v] = u;
            depth_node[v] = depth_node[u] + 1;
            order.push_back(v);
        }
    }

    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i <= n; i++) {
            up[j][i] = up[j - 1][up[j - 1][i]];
        }
    }
}

int lca(int u, int v) {
    if (depth_node[u] < depth_node[v]) {
        swap(u, v);
    }
    int diff = depth_node[u] - depth_node[v];
    for (int j = 0; j < LOG; j++) {
        if (diff & (1 << j)) {
            u = up[j][u];
        }
    }
    if (u == v) {
        return u;
    }
    for (int j = LOG - 1; j >= 0; j--) {
        if (up[j][u] != up[j][v]) {
            u = up[j][u];
            v = up[j][v];
        }
    }
    return up[0][u];
}

void build_depth_rmq() {
    for (int i = 2; i <= n; i++) {
        depth_log[i] = depth_log[i >> 1] + 1;
    }
    for (int i = 1; i <= n; i++) {
        depth_st[0][i] = depth_node[i];
    }
    for (int j = 1; j < LOG; j++) {
        int len = 1 << j;
        for (int i = 1; i + len - 1 <= n; i++) {
            depth_st[j][i] = max(depth_st[j - 1][i], depth_st[j - 1][i + (len >> 1)]);
        }
    }
}

int query_depth_max(int l, int r) {
    int len = r - l + 1;
    int lg = depth_log[len];
    return max(depth_st[lg][l], depth_st[lg][r - (1 << lg) + 1]);
}

bool cmp_position_by_value(int a, int b) {
    if (value_id[a] != value_id[b]) {
        return value_id[a] > value_id[b];
    }
    return a < b;
}

void solve_parallel_binary_search() {
    int total_values = (int)values.size();
    int total_queries = (int)queries.size();
    if (total_queries == 0) {
        return;
    }

    for (int i = 0; i < total_queries; i++) {
        low_bound_idx[i] = 0;
        high_bound_idx[i] = total_values - 1;
        answer_idx[i] = 0;
    }

    int edge_count = n - 1;
    for (int i = 1; i <= edge_count; i++) {
        position_order[i] = i;
    }
    sort(position_order + 1, position_order + edge_count + 1, cmp_position_by_value);

    build_seg(1, 1, edge_count);

    bool changed = true;
    while (changed) {
        changed = false;
        used_bucket.clear();

        for (int i = 0; i < total_queries; i++) {
            if (low_bound_idx[i] <= high_bound_idx[i]) {
                changed = true;
                int mid = (low_bound_idx[i] + high_bound_idx[i]) >> 1;
                if (bucket_head[mid] == -1) {
                    used_bucket.push_back(mid);
                }
                bucket_next[i] = bucket_head[mid];
                bucket_head[mid] = i;
            }
        }

        if (!changed) {
            break;
        }

        reset_seg(1, 1, edge_count);
        int ptr = 1;

        for (int value_index = total_values - 1; value_index >= 0; value_index--) {
            while (ptr <= edge_count && value_id[position_order[ptr]] >= value_index) {
                activate_position(1, 1, edge_count, position_order[ptr]);
                ptr++;
            }

            for (int idx = bucket_head[value_index]; idx != -1; idx = bucket_next[idx]) {
                Query qu = queries[idx];
                SegNode res = query_seg(1, 1, edge_count, qu.left, qu.right);
                if (res.best >= qu.need) {
                    answer_idx[idx] = value_index;
                    low_bound_idx[idx] = value_index + 1;
                } else {
                    high_bound_idx[idx] = value_index - 1;
                }
            }
        }

        for (int i = 0; i < (int)used_bucket.size(); i++) {
            bucket_head[used_bucket[i]] = -1;
        }
    }

    for (int i = 0; i < total_queries; i++) {
        answer[queries[i].id] = values[answer_idx[i]];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }

    build_lca();
    build_depth_rmq();

    if (n > 1) {
        values.reserve(n - 1);
        for (int i = 1; i < n; i++) {
            adjacent_depth[i] = depth_node[lca(i, i + 1)];
            values.push_back(adjacent_depth[i]);
        }
        sort(values.begin(), values.end());
        values.erase(unique(values.begin(), values.end()), values.end());

        for (int i = 1; i < n; i++) {
            value_id[i] = lower_bound(values.begin(), values.end(), adjacent_depth[i]) - values.begin();
        }
        for (int i = 0; i < (int)values.size(); i++) {
            bucket_head[i] = -1;
        }
    }

    cin >> q;
    for (int id = 1; id <= q; id++) {
        int l, r, k;
        cin >> l >> r >> k;
        if (k == 1) {
            answer[id] = query_depth_max(l, r);
        } else {
            Query qu;
            qu.left = l;
            qu.right = r - 1;
            qu.need = k - 1;
            qu.id = id;
            queries.push_back(qu);
        }
    }

    if (n > 1) {
        solve_parallel_binary_search();
    }

    for (int i = 1; i <= q; i++) {
        cout << answer[i] << '\n';
    }

    return 0;
}

复杂度

LCA 倍增预处理和深度 ST 表都是 $O(n log n)$ 。

并行二分有 $O(log n)$ 轮，每轮线段树激活位置和回答询问的总复杂度为 $O((n+q) \log n)$ ，所以总时间复杂度为：

$O((n+q) \log^2 n)$

空间复杂度为 $O(n log n + q)$ 。

总结

本题最关键的一步是发现连续编号区间 [L, R] 的 LCA 深度等于相邻数组 b[L..R-1] 的最小值。这样原来的树上区间 LCA 查询就转成了“区间中是否存在足够长的连续可行段”。

k = 1 要单独处理，因为单点区间没有相邻数组位置。k >= 2 时，用离线二分答案和线段树维护连续激活段，就可以批量回答所有询问。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P11364 [NOIP2024] 树上查询

题目描述

有一天小 S 和她的朋友小 N 一起研究一棵包含了 $n$ 个结点的树。

这是一棵有根树，根结点编号为 $1$ ，每个结点 $u$ 的深度 $\text{dep}_ u$ 定义为 $u$ 到 $1$ 的简单路径上的结点数量。

除此之外，再定义 $\text{LCA*}(l, r)$ 为编号在 $[l, r]$ 中所有结点的最近公共祖先，即 $l, l + 1, \dots , r$ 的公共祖先结点中深度最大的结点。

小 N 对这棵树提出了 $q$ 个询问。在每个询问中，小 N 都会给出三个参数 $l, r, k$ ，表示他想知道 $[l, r]$ 中任意长度大于等于 $k$ 的连续子区间的最近公共祖先深度的最大值，即

\max_{l\le l'\le r'\le r \land r'-l'+1\ge k}\text{dep}_ {\text{LCA*}(l', r')}

你的任务是帮助小 S 来回答这些询问。

输入格式

输入的第一行包含一个正整数 $n$ ，表示树的结点数。

接下来 $n - 1$ 行，每行包含两个正整数 $u, v$ ，表示存在一条从结点 $u$ 到结点 $v$ 的边。

第 $n + 1$ 行包含一个正整数 $q$ ，表示询问的数量。

接下来 $q$ 行，每行包含三个正整数 $l, r, k$ ，描述了一次询问。

输出格式

对于每次询问输出一行，包含一个整数，表示对应的答案。

输入输出样例 #1

输入 #1

text

输出 #1

text

说明/提示

【样例 1 解释】

对于第一组询问， $\text{LCA*}(2, 3) = 2, \text{LCA*}(3, 4) = 2, \text{LCA*}(4, 5) = 6$ ， $2$ 的深度为 $3$ ， $6$ 的深度为 $2$ ，因此答案为 $\max\{3, 3, 2\} = 3$ 。
对于第二组询问，答案为 $1, 2, 3, 4$ 四个结点的最大深度，因此答案为 $4$ 。
对于第三组询问， $\text{LCA*}(1, 3) = 1, \text{LCA*}(2, 4) = 2, \text{LCA*}(3, 5) = 6, \text{LCA*}(4, 6) = 6$ ，依旧是 $2$ 的深度最大，因此答案为 $3$ 。

【样例 2】

见附件的 query/query2.in 与 query/query2.ans。

该样例满足 $n, q ≤ 500$ 。

【样例 3】

见附件的 query/query3.in 与 query/query3.ans。

该样例满足 $n, q ≤ 10^5$ 且树符合链的形态。

【样例 4】

见附件的 query/query4.in 与 query/query4.ans。

该样例满足 $n, q ≤ 5 × 10^5$ 。

【数据范围】

对于所有的测试数据，保证：$1 ≤ n, q ≤ 5 × 10^5 , 1 ≤ l ≤ r ≤ n, 1 ≤ k ≤ r - l + 1$。

::cute-table{tuack}

测试点编号	$n,q\le$	特殊限制
$1\sim2$	$500$	无
$3\sim5$	$5000$	^
$6\sim9$	$10^5$	满足性质 A
$10\sim13$	$5\times10^5$	^
$14\sim16$	^	满足性质 B
$17\sim20$	$10^5$	无
$21\sim25$	$5\times10^5$	^

性质 A：保证输入的树符合链的形态，且根结点的度数为 $1$ 。

性质 B：对于每个询问保证 $k = r - l + 1$ 。

[NOIP2024] 树上查询

目录

题意

思路

代码

复杂度

总结

一图流解析