✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线200+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

得物-2026.03.21-第二套

得物-2026.03.21-第二套

这套题的节奏是“树上基础查询 -> 树上结构分析 -> 序列 DP”。第一题是标准倍增热身，第二题区分度最高，关键在于把“删两个点”后的最大连通块拆成几类固定部分，第三题则是经典双调子序列模型。

第 1 题：第 级上家查询

题意很直接，就是多次查询第 级祖先。
把整棵树按父子关系建出来后，直接做二进制倍增。每次询问按 的二进制位往上跳，复杂度是 。

第 2 题：拆去两点后的最大连块

选两个点，把和它们相连的边全拆掉，要求剩下最大的连通块尽量小。
更稳的切入点是先固定一个被拆点，再看另一点只会打碎自己所在的那棵侧枝树。这样每次固定后都能线性求完，整体复杂度是 。

第 3 题：最长观景回折路线

要求选出的景点编号递增，同时高度先不降再不升。
这其实就是“最长双调子序列”的非严格版本：先求每个位置结尾的最长非降子序列，再求每个位置开头的最长非升子序列，最后合并即可。

1. 第 级上家查询

问题描述

小基 在整理一份单向传承关系表。共有 个节点，其中只有 号节点没有上级，其他每个节点都恰好有一个直接上级。

如果节点 的直接上级是 ，那么：

• 级祖先就是它的直接上级。
• 级祖先就是它的 级祖先的直接上级。

现在给出多次询问，每次询问一个节点 和整数 ，请输出它的 级祖先编号。
如果已经无法继续向上追溯，就输出 。

输入格式

• 第一行两个整数 ，表示节点数和询问数。
• 第二行给出 个整数 ，其中 表示节点 的直接上级编号。
• 接下来 行，每行两个整数 ，表示一次询问。

输出格式

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

样例输入

5 3
1 2 3 4
5 1
1 1
5 3

样例输出

4
0
2

数据范围

样例	解释说明
样例 1	结构是一条链 。因此 的第 级上家是 ， 再往上已经没有上家，所以输出 ，而 的第 级上家是 。

题解

每次都顺着父亲指针往上跳，最坏要跳 次。
当 也很大时，这样会超时。

这道题的标准做法是二进制倍增。

状态含义

设 表示节点 的 级祖先。

那么：

• 就是节点 的直接上级。
• 就是节点 的 级祖先。
• 就是节点 的 级祖先。

如果某一级祖先不存在，就记成 。

预处理转移

因为 ，所以可以先跳一半，再跳一半：

也就是说，想知道 级祖先，只需要知道两个 级祖先的信息。

如何回答询问

把 写成二进制。

如果第 位是 ，就让当前节点往上跳 层。
这样一轮询问最多只会跳 次。

例如要找第 级祖先，因为：

那就依次跳 、、 层。

为什么这样不会漏

任意一个正整数都能唯一拆成若干个不同的 的幂次之和。
所以把 按二进制拆开以后，刚好覆盖了“往上跳 层”的全部过程，而且不会重复计算。

复杂度分析

• 预处理复杂度：
• 单次询问复杂度：
• 总复杂度：
• 空间复杂度：

参考代码

• Python

import sys

input = lambda:sys.stdin.readline().strip()


def solve():
    n, q = map(int, input().split())
    fa = [0] + [0] + list(map(int, input().split()))

    lg = n.bit_length()
    up = [[0] * (n + 1) for _ in range(lg)]

    # 第 0 层就是直接父亲。
    for i in range(1, n + 1):
        up[0][i] = fa[i]

    # 倍增预处理。
    for j in range(1, lg):
        pre = up[j - 1]
        cur = up[j]
        for i in range(1, n + 1):
            cur[i] = pre[pre[i]]

    out = []
    for _ in range(q):
        x, k = map(int, input().split())

        # 按 k 的二进制位依次向上跳。
        bit = 0
        while k and x:
            if k & 1:
                x = up[bit][x]
            k >>= 1
            bit += 1

        out.append(str(x))

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()

• Cpp

#include <bits/stdc++.h>
using namespace std;

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

    int n, q;
    cin >> n >> q;

    vector<int> fa(n + 1, 0);
    for (int i = 2; i <= n; ++i) {
        cin >> fa[i];
    }

    int lg = 0;
    while ((1 << lg) <= n) {
        ++lg;
    }

    vector<vector<int>> up(lg, vector<int>(n + 1, 0));

    // up[0][i] 表示直接父亲。
    for (int i = 1; i <= n; ++i) {
        up[0][i] = fa[i];
    }

    // 构造每个 2^j 级祖先。
    for (int j = 1; j < lg; ++j) {
        for (int i = 1; i <= n; ++i) {
            up[j][i] = up[j - 1][up[j - 1][i]];
        }
    }

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

        // 把 k 拆成若干个 2 的幂次。
        for (int j = 0; j < lg && x; ++j) {
            if ((k >> j) & 1) {
                x = up[j][x];
            }
        }

        cout << x << '\n';
    }
    return 0;
}

• Java

import java.io.BufferedInputStream;
import java.io.IOException;

public class Main {
    static class FastScanner {
        private final BufferedInputStream in = new BufferedInputStream(System.in);
        private final byte[] buf = new byte[1 << 16];
        private int len = 0;
        private int ptr = 0;

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buf);
                ptr = 0;
                if (len <= 0) {
                    return -1;
                }
            }
            return buf[ptr++];
        }

        int nextInt() throws IOException {
            int c;
            while ((c = read()) <= ' ') {
                if (c == -1) {
                    return -1;
                }
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int val = 0;
            while (c > ' ') {
                val = val * 10 + c - '0';
                c = read();
            }
            return val * sgn;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner();
        int n = fs.nextInt();
        int q = fs.nextInt();

        int[] fa = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            fa[i] = fs.nextInt();
        }

        int lg = 0;
        while ((1 << lg) <= n) {
            lg++;
        }

        int[][] up = new int[lg][n + 1];

        // 第 0 层倍增表就是直接父亲。
        for (int i = 1; i <= n; i++) {
            up[0][i] = fa[i];
        }

        // 按层递推更高的祖先信息。
        for (int j = 1; j < lg; j++) {
            for (int i = 1; i <= n; i++) {
                up[j][i] = up[j - 1][up[j - 1][i]];
            }
        }

        StringBuilder sb = new StringBuilder();
        while (q-- > 0) {
            int x = fs.nextInt();
            int k = fs.nextInt();

            // 遇到二进制中为 1 的位，就跳对应层数。
            for (int j = 0; j < lg && x != 0; j++) {
                if (((k >> j) & 1) == 1) {
                    x = up[j][x];
                }
            }

            sb.append(x).append('\n');
        }

        System.out.print(sb);
    }
}

2. 拆杆后的最小最大块

问题描述

小基 用 块积木和 根连接杆拼成了一棵树。积木编号为 ，并且整套结构连通。

现在她可以任选两块积木，把与这两块积木直接相连的所有连接杆全部拆掉。操作结束后，整棵树会分成若干个连通块，而这两块被选中的积木也会各自单独成为大小为 的连通块。

小基 想让“最大的那个连通块”尽量小。
请计算这个最小可能值。

输入格式

• 第一行一个整数 ，表示积木数量。
• 第二行给出 个整数 ，其中 表示编号为 的积木与编号为 的积木之间有一根连接杆。

输出格式

输出一个整数，表示最小可能的最大连通块大小。

样例输入

5
1 1 2 3

样例输出

1

数据范围

• 
• 输入保证这 个点构成一棵树

样例	解释说明
样例 1	边为 、、、。如果拆掉积木 和 ，剩下的连通块分别是 、、 以及两个被选中的单点，因此最大的连通块大小是 。

题解

如果直接枚举两块积木，再重新扫一遍整棵树的连通块，复杂度会到 ，在 时不够稳。

更合适的切法是先固定其中一个被拆掉的点，记作 。

删掉 以后，原树会沿着 的每条相邻边裂成若干棵互不相连的“侧枝树”。
这时再删除另一个点 ，只会继续影响 所在的那一棵侧枝，其他侧枝的大小完全不会变。

所以对于固定的 ，需要做两件事：

1. 求出删掉 后，每棵侧枝树的大小。
2. 对每个 ，求出在自己的侧枝里再删掉 以后，最大的残余连通块大小。

设某棵侧枝树大小为 ，并把它随便定一个根。
如果删除这棵侧枝里的结点 ，留下来的部分只会来自两类位置：

• 的若干个儿子子树，大小就是对应的子树大小。
• 往父亲方向剩下来的那一大块，大小是 。

因此，删掉 以后，这棵侧枝内部最大的连通块就是：

与此同时，除了 所在侧枝以外，其他侧枝里最大的那一棵也要算进答案。
把这两部分取最大值，再和单点大小 比较一下，就是删掉 后的最终结果。

对每个 做一遍这样的统计，总复杂度是 。

• 时间复杂度：
• 空间复杂度：

参考代码

• Python

import sys

input = lambda:sys.stdin.readline().strip()


def solve() -> None:
    n = int(input())
    pa = list(map(int, input().split()))

    g = [[] for _ in range(n + 1)]
    for i, p in enumerate(pa, 2):
        g[p].append(i)
        g[i].append(p)

    sid = [-1] * (n + 1)
    sub = [0] * (n + 1)
    val = [0] * (n + 1)
    par = [0] * (n + 1)
    ans = n

    for ban in range(1, n + 1):
        szs = []

        # ban 的每个邻居都会形成一棵侧枝树。
        for rt in g[ban]:
            cid = len(szs)
            stk = [rt]
            ords = []
            par[rt] = ban
            sid[rt] = cid

            while stk:
                x = stk.pop()
                ords.append(x)
                for y in g[x]:
                    if y == ban or y == par[x]:
                        continue
                    par[y] = x
                    sid[y] = cid
                    stk.append(y)

            sz = len(ords)
            szs.append(sz)

            # 反向扫一遍，就能拿到这棵侧枝里的子树大小。
            for x in reversed(ords):
                tot = 1
                mx = 0
                for y in g[x]:
                    if y == ban or y == par[x]:
                        continue
                    tot += sub[y]
                    if sub[y] > mx:
                        mx = sub[y]
                sub[x] = tot
                rem = sz - tot
                if rem > mx:
                    mx = rem
                val[x] = mx

        best1 = 0
        best2 = 0
        cnt1 = 0
        for sz in szs:
            if sz > best1:
                best2 = best1
                best1 = sz
                cnt1 = 1
            elif sz == best1:
                cnt1 += 1
            elif sz > best2:
                best2 = sz

        for x in range(1, n + 1):
            if x == ban:
                continue
            cur_sz = szs[sid[x]]
            oth = best1
            if cur_sz == best1 and cnt1 == 1:
                oth = best2
            cur = val[x]
            if oth > cur:
                cur = oth
            if cur < 1:
                cur = 1
            if cur < ans:
                ans = cur

    print(ans)


if __name__ == "__main__":
    solve()

• Cpp

#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;

    vector<vector<int>> g(n + 1);
    for (int i = 2; i <= n; ++i) {
        int p;
        cin