精选16-35道信奥赛C++算法题

信奥赛算法练习题。以下是另外20道完整题目，包含题目描述、输入输出格式、样例和C++参考代码。

📝 七、字符串算法

16. KMP字符串匹配

题目描述：给定一个文本串S和一个模式串P，找出P在S中所有出现的位置。
输入格式：

• 第一行：一个字符串S

• 第二行：一个字符串P
  输出格式：所有匹配位置的起始下标（从0开始），用空格隔开
  样例输入：

text

ababcabcabababd
ababd

样例输出：

text

10

C++代码：

cpp

#include <iostream>#include <string>#include <vector>using namespace std;vector<int> computeLPS(const string& pattern) {
    int m = pattern.length();
    vector<int> lps(m, 0);
    int len = 0;
    int i = 1;
    
    while (i < m) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;}vector<int> kmpSearch(const string& text, const string& pattern) {
    vector<int> positions;
    int n = text.length();
    int m = pattern.length();
    
    if (m == 0) return positions;
    
    vector<int> lps = computeLPS(pattern);
    int i = 0;  // text的索引
    int j = 0;  // pattern的索引
    
    while (i < n) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }
        
        if (j == m) {
            positions.push_back(i - j);
            j = lps[j - 1];
        } else if (i < n && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    
    return positions;}int main() {
    string text, pattern;
    getline(cin, text);
    getline(cin, pattern);
    
    vector<int> result = kmpSearch(text, pattern);
    
    for (int i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i < result.size() - 1) cout << " ";
    }
    if (result.empty()) {
        cout << "-1";
    }
    cout << endl;
    
    return 0;}

17. 字符串哈希

题目描述：给定一个字符串，多次询问某两个子串是否完全相同。
输入格式：

• 第一行：一个字符串s

• 第二行：一个整数q

• 接下来q行：每行四个整数l1, r1, l2, r2
  输出格式：对于每个询问，输出一行"Yes"或"No"
  样例输入：

text

abacaba
3
1 1 7 7
1 2 5 6
2 3 4 5

样例输出：

text

Yes
No
Yes

C++代码：

cpp

#include <iostream>#include <string>#include <vector>using namespace std;typedef unsigned long long ULL;const int P = 131;  // 进制基数vector<ULL> h, p;void init_hash(const string& s) {
    int n = s.length();
    h.resize(n + 1);
    p.resize(n + 1);
    
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        h[i] = h[i - 1] * P + (s[i - 1] - 'a' + 1);
        p[i] = p[i - 1] * P;
    }}ULL get_hash(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];}int main() {
    string s;
    cin >> s;
    
    init_hash(s);
    
    int q;
    cin >> q;
    
    while (q--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        
        ULL hash1 = get_hash(l1, r1);
        ULL hash2 = get_hash(l2, r2);
        
        if (hash1 == hash2) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    
    return 0;}

18. 最长回文子串（Manacher算法）

题目描述：给定一个字符串，求它的最长回文子串的长度。
输入格式：一个字符串s（长度 ≤ 10^6）
输出格式：一个整数，表示最长回文子串的长度
样例输入：

text

abacab

样例输出：

text

5

C++代码：

cpp

#include <iostream>#include <string>#include <vector>#include <algorithm>using namespace std;int manacher(const string& s) {
    // 预处理字符串
    string t = "#";
    for (char c : s) {
        t += c;
        t += '#';
    }
    
    int n = t.length();
    vector<int> p(n, 0);
    int center = 0, right = 0;
    int max_len = 0;
    
    for (int i = 1; i < n - 1; i++) {
        // 利用对称性
        int mirror = 2 * center - i;
        
        if (i < right) {
            p[i] = min(right - i, p[mirror]);
        }
        
        // 中心扩展
        while (i + p[i] + 1 < n && i - p[i] - 1 >= 0 &&
               t[i + p[i] + 1] == t[i - p[i] - 1]) {
            p[i]++;
        }
        
        // 更新中心和右边界
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
        
        max_len = max(max_len, p[i]);
    }
    
    return max_len;  // 返回的是原始字符串的最长回文子串长度}int main() {
    string s;
    cin >> s;
    
    cout << manacher(s) << endl;
    
    return 0;}

🧠 八、动态规划（进阶）

19. 编辑距离

题目描述：给定两个字符串A和B，求将A转换为B所需的最少操作次数。允许的操作有：插入一个字符、删除一个字符、替换一个字符。
输入格式：

• 第一行：字符串A

• 第二行：字符串B
  输出格式：一个整数，表示编辑距离
  样例输入：

text

horse
ros

样例输出：

text

3

C++代码：

cpp

#include <iostream>#include <string>#include <vector>#include <algorithm>using namespace std;int editDistance(const string& A, const string& B) {
    int m = A.length();
    int n = B.length();
    
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    // 初始化
    for (int i = 0; i <= m; i++) {
        dp[i][0] = i;  // 删除i个字符
    }
    for (int j = 0; j <= n; j++) {
        dp[0][j] = j;  // 插入j个字符
    }
    
    // 动态规划
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (A[i - 1] == B[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = min({dp[i - 1][j],      // 删除
                               dp[i][j - 1],      // 插入
                               dp[i - 1][j - 1]}) // 替换
                           + 1;
            }
        }
    }
    
    return dp[m][n];}int main() {
    string A, B;
    cin >> A >> B;
    
    cout << editDistance(A, B) << endl;
    
    return 0;}

20. 最长公共子序列（LCS）

题目描述：给定两个字符串，求它们的最长公共子序列的长度。
输入格式：

• 第一行：字符串A

• 第二行：字符串B
  输出格式：一个整数，表示LCS长度
  样例输入：

text

abcde
ace

样例输出：

text

3

C++代码：

cpp

#include <iostream>#include <string>#include <vector>#include <algorithm>using namespace std;int lcs(const string& A, const string& B) {
    int m = A.length();
    int n = B.length();
    
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (A[i - 1] == B[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    return dp[m][n];}int main() {
    string A, B;
    cin >> A >> B;
    
    cout << lcs(A, B) << endl;
    
    return 0;}

21. 完全背包问题

题目描述：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。
输入格式：

• 第一行：两个整数N, V

• 接下来N行：每行两个整数c[i], w[i]
  输出格式：一个整数，表示最大价值
  样例输入：

text

4 10
2 1
3 3
4 5
7 9

样例输出：

text

12

C++代码：

cpp

#include <iostream>#include <vector>#include <algorithm>using namespace std;int completePack(int N, int V, vector<int>& c, vector<int>& w) {
    vector<int> dp(V + 1, 0);
    
    for (int i = 0; i < N; i++) {
        // 完全背包：正序遍历
        for (int j = c[i]; j <= V; j++) {
            dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
        }
    }
    
    return dp[V];}int main() {
    int N, V;
    cin >> N >> V;
    
    vector<int> c(N), w(N);
    for (int i = 0; i < N; i++) {
        cin >> c[i] >> w[i];
    }
    
    cout << completePack(N, V, c, w) << endl;
    
    return 0;}

22. 多重背包问题

题目描述：有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件体积是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。
输入格式：

• 第一行：两个整数N, V

• 接下来N行：每行三个整数c[i], w[i], n[i]
  输出格式：一个整数，表示最大价值
  样例输入：

text

4 10
2 1 2
3 3 1
4 5 3
7 9 1

样例输出：

text

11

C++代码：

cpp

#include <iostream>#include <vector>#include <algorithm>using namespace std;int multiplePack(int N, int V, vector<int>& c, vector<int>& w, vector<int>& n) {
    vector<int> dp(V + 1, 0);
    
    for (int i = 0; i < N; i++) {
        // 二进制优化
        int num = min(n[i], V / c[i]);
        for (int k = 1; num > 0; k <<= 1) {
            if (k > num) k = num;
            num -= k;
            int cost = c[i] * k;
            int value = w[i] * k;
            
            // 0-1背包：倒序遍历
            for (int j = V; j >= cost; j--) {
                dp[j] = max(dp[j], dp[j - cost] + value);
            }
        }
    }
    
    return dp[V];}int main() {
    int N, V;
    cin >> N >> V;
    
    vector<int> c(N), w(N), n(N);
    for (int i = 0; i < N; i++) {
        cin >> c[i] >> w[i] >> n[i];
    }
    
    cout << multiplePack(N, V, c, w, n) << endl;
    
    return 0;}

23. 石子合并（区间DP）

题目描述：有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子合并成为一堆。合并的过程只能每次将相邻的两堆石子合并成一堆，合并的代价为这两堆石子的数量之和。找出一种合理的方法，使总的代价最小。
输入格式：

• 第一行：一个整数N

• 第二行：N个整数，表示每堆石子的数量
  输出格式：一个整数，表示最小代价
  样例输入：

text

4
1 3 5 2

样例输出：

text

22

C++代码：

cpp

#include <iostream>#include <vector>#include <climits>#include <algorithm>using namespace std;int stoneMerge(int N, vector<int>& stones) {
    // 前缀和
    vector<int> prefix(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        prefix[i] = prefix[i - 1] + stones[i - 1];
    }
    
    // dp[i][j]表示合并第i到第j堆石子的最小代价
    vector<vector<int>> dp(N, vector<int>(N, 0));
    
    // 区间长度从2开始
    for (int len = 2; len <= N; len++) {
        for (int i = 0; i + len - 1 < N; i++) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;
            
            // 枚举分割点
            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k + 1][j] + prefix[j + 1] - prefix[i];
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }
    
    return dp[0][N - 1];}int main() {
    int N;
    cin >> N;
    
    vector<int> stones(N);
    for (int i = 0; i < N; i++) {
        cin >> stones[i];
    }
    
    cout << stoneMerge(N, stones) << endl;
    
    return 0;}

🗺️ 九、图论（进阶）

24. 拓扑排序

题目描述：给定一个有向图，判断是否存在拓扑排序，如果存在则输出一个拓扑序列。
输入格式：

• 第一行：两个整数n, m，表示顶点数和边数

• 接下来m行：每行两个整数u, v，表示一条有向边u->v
  输出格式：如果存在拓扑排序，输出任意一个拓扑序列；否则输出"-1"
  样例输入：

text

5 4
1 2
1 3
2 4
3 4

样例输出：

text

1 2 3 4 5

C++代码：

cpp

#include <iostream>#include <vector>#include <queue>using namespace std;vector<int> topologicalSort(int n, vector<vector<int>>& graph, vector<int>& inDegree) {
    vector<int> result;
    queue<int> q;
    
    // 将入度为0的顶点加入队列
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(u);
        
        for (int v : graph[u]) {
            inDegree[v]--;
            if (inDegree[v] == 0) {
                q.push(v);
            }
        }
    }
    
    if (result.size() != n) {
        return {};  // 存在环
    }
    
    return result;}int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> graph(n + 1);
    vector<int> inDegree(n + 1, 0);
    
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        inDegree[v]++;
    }
    
    vector<int> result = topologicalSort(n, graph, inDegree);
    
    if (result.empty()) {
        cout << "-1" << endl;
    } else {
        for (int i = 0; i < n; i++) {
            cout << result[i];
            if (i < n - 1) cout << " ";
        }
        cout << endl;
    }
    
    return 0;}

25. 二分图最大匹配（匈牙利算法）

题目描述：给定一个二分图，求其最大匹配数。
输入格式：

• 第一行：三个整数n, m, e，分别表示左部点数、右部点数和边数

• 接下来e行：每行两个整数u, v，表示左部点u和右部点v之间有一条边
  输出格式：一个整数，表示最大匹配数
  样例输入：

text

4 4 7
1 1
1 2
1 3
2 1
2 3
3 2
4 2

样例输出：

text

3

C++代码：

cpp

#include <iostream>#include <vector>#include <cstring>using namespace std;class BipartiteMatching {private:
    int n, m;
    vector<vector<int>> graph;
    vector<int> matchR;  // 右部点的匹配
    vector<bool> visited;
    
    bool dfs(int u) {
        for (int v : graph[u]) {
            if (!visited[v]) {
                visited[v] = true;
                if (matchR[v] == -1 || dfs(matchR[v])) {
                    matchR[v] = u;
                    return true;
                }
            }
        }
        return false;
    }
    public:
    BipartiteMatching(int n, int m) : n(n), m(m) {
        graph.resize(n + 1);
        matchR.resize(m + 1, -1);
    }
    
    void addEdge(int u, int v) {
        graph[u].push_back(v);
    }
    
    int maxMatching() {
        int result = 0;
        for (int u = 1; u <= n; u++) {
            visited.assign(m + 1, false);
            if (dfs(u)) {
                result++;
            }
        }
        return result;
    }};int main() {
    int n, m, e;
    cin >> n >> m >> e;
    
    BipartiteMatching bm(n, m);
    
    for (int i = 0; i < e; i++) {
        int u, v;
        cin >> u >> v;
        bm.addEdge(u, v);
    }
    
    cout << bm.maxMatching() << endl;
    
    return 0;}

26. 最短路径（Floyd算法）

题目描述：给定一个有向图，求所有顶点对之间的最短路径。
输入格式：

• 第一行：两个整数n, m

• 接下来m行：每行三个整数u, v, w

• 接下来一行：一个整数k，表示询问次数

• 接下来k行：每行两个整数x, y
  输出格式：对于每个询问，输出从x到y的最短路径长度。如果不可达，输出"-1"
  样例输入：

text

4 4
1 2 1
2 3 2
3 4 3
1 4 10
3
1 4
2 3
4 1

样例输出：

text

6
2
-1

C++代码：

cpp

#include <iostream>#include <vector>#include <climits>#include <algorithm>using namespace std;const long long INF = 1e18;void floydWarshall(vector<vector<long long>>& dist, int n) {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][k] < INF && dist[k][j] < INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }}int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<long long>> dist(n + 1, vector<long long>(n + 1, INF));
    
    // 初始化
    for (int i = 1; i <= n; i++) {
        dist[i][i] = 0;
    }
    
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        dist[u][v] = min(dist[u][v], (long long)w);
    }
    
    floydWarshall(dist, n);
    
    int k;
    cin >> k;
    
    for (int i = 0; i < k; i++) {
        int x, y;
        cin >> x >> y;
        
        if (dist[x][y] == INF) {
            cout << "-1" << endl;
        } else {
            cout << dist[x][y] << endl;
        }
    }
    
    return 0;}

27. 强连通分量（Kosaraju算法）

题目描述：给定一个有向图，求其强连通分量的个数。
输入格式：

• 第一行：两个整数n, m

• 接下来m行：每行两个整数u, v
  输出格式：一个整数，表示强连通分量的个数
  样例输入：

text

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

样例输出：

text

3

C++代码：

cpp

#include <iostream>#include <vector>#include <stack>#include <algorithm>using namespace std;class Kosaraju {private:
    int n;
    vector<vector<int>> graph, reverseGraph;
    vector<bool> visited;
    stack<int> order;
    vector<int> component;
    
    void dfs1(int u) {
        visited[u] = true;
        for (int v : graph[u]) {
            if (!visited[v]) {
                dfs1(v);
            }
        }
        order.push(u);
    }
    
    void dfs2(int u, int compId) {
        component[u] = compId;
        for (int v : reverseGraph[u]) {
            if (component[v] == -1) {
                dfs2(v, compId);
            }
        }
    }
    public:
    Kosaraju(int n) : n(n) {
        graph.resize(n + 1);
        reverseGraph.resize(n + 1);
        visited.resize(n + 1, false);
        component.resize(n + 1, -1);
    }
    
    void addEdge(int u, int v) {
        graph[u].push_back(v);
        reverseGraph[v].push_back(u);
    }
    
    int countSCC() {
        // 第一次DFS：获取拓扑序
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                dfs1(i);
            }
        }
        
        // 第二次DFS：在反图上遍历
        int compId = 0;
        while (!order.empty()) {
            int u = order.top();
            order.pop();
            if (component[u] == -1) {
                dfs2(u, compId++);
            }
        }
        
        return compId;
    }};int main() {
    int n, m;
    cin >> n >> m;
    
    Kosaraju kosaraju(n);
    
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        kosaraju.addEdge(u, v);
    }
    
    cout << kosaraju.countSCC() << endl;
    
    return 0;}

📊 十、树相关算法

28. 树的直径

题目描述：给定一棵树，求这棵树的直径长度（树上最远两点的距离）。
输入格式：

• 第一行：一个整数n，表示节点数

• 接下来n-1行：每行三个整数u, v, w，表示一条边
  输出格式：一个整数，表示树的直径
  样例输入：

text

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

样例输出：

text

6

C++代码：

cpp

#include <iostream>#include <vector>#include <cstring>#include <algorithm>using namespace std;struct Edge {
    int to;
    int weight;};pair<int, int> dfs(int u, int parent, const vector<vector<Edge>>& tree) {
    int maxDist = 0;
    int farthestNode = u;
    
    for (const Edge& edge : tree[u]) {
        if (edge.to != parent) {
            auto [dist, node] = dfs(edge.to, u, tree);
            dist += edge.weight;
            if (dist > maxDist) {
                maxDist = dist;
                farthestNode = node;
            }
        }
    }
    
    return {maxDist, farthestNode};}int treeDiameter(const vector<vector<Edge>>& tree, int n) {
    // 第一次DFS：从任意点（1）出发找到最远点
    auto [_, farthest] = dfs(1, -1, tree);
    
    // 第二次DFS：从最远点出发找到直径
    auto [diameter, __] = dfs(farthest, -1, tree);
    
    return diameter;}int main() {
    int n;
    cin >> n;
    
    vector<vector<Edge>> tree(n + 1);
    
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        tree[u].push_back({v, w});
        tree[v].push_back({u, w});
    }
    
    cout << treeDiameter(tree, n) << endl;
    
    return 0;}

29. 树的重心

题目描述：给定一棵树，求这棵树的重心。重心是指树中的一个节点，如果将这个点删除后，剩余各个连通块中点数的最大值最小。
输入格式：

• 第一行：一个整数n

• 接下来n-1行：每行两个整数u, v
  输出格式：输出重心的编号（如果有多个，输出编号最小的）
  样例输入：

text

7
1 2
1 3
1 4
2 5
2 6
4 7

样例输出：

text

1

C++代码：

cpp

#include <iostream>#include <vector>#include <algorithm>using namespace std;class TreeCenter {private:
    int n;
    vector<vector<int>> tree;
    vector<int> size;
    vector<int> maxComponent;
    int center, minMaxComponent;
    
    void dfs(int u, int parent) {
        size[u] = 1;
        maxComponent[u] = 0;
        
        for (int v : tree[u]) {
            if (v != parent) {
                dfs(v, u);
                size[u] += size[v];
                maxComponent[u] = max(maxComponent[u], size[v]);
            }
        }
        
        // 考虑父节点方向的部分
        maxComponent[u] = max(maxComponent[u], n - size[u]);
        
        if (maxComponent[u] < minMaxComponent ||
            (maxComponent[u] == minMaxComponent && u < center)) {
            minMaxComponent = maxComponent[u];
            center = u;
        }
    }
    public:
    TreeCenter(int n) : n(n) {
        tree.resize(n + 1);
        size.resize(n + 1);
        maxComponent.resize(n + 1);
        minMaxComponent = n + 1;
        center = -1;
    }
    
    void addEdge(int u, int v) {
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    
    int findCenter() {
        dfs(1, -1);
        return center;
    }};int main() {
    int n;
    cin >> n;
    
    TreeCenter tc(n);
    
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        tc.addEdge(u, v);
    }
    
    cout << tc.findCenter() << endl;
    
    return 0;}

30. 最近公共祖先（LCA）

题目描述：给定一棵树和若干询问，每次询问两个节点的最近公共祖先。
输入格式：

• 第一行：三个整数n, m, root

• 接下来n-1行：每行两个整数u, v

• 接下来m行：每行两个整数x, y
  输出格式：对于每个询问，输出一个整数表示答案
  样例输入：

text

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

样例输出：

text

2
1
1

C++代码：

cpp

#include <iostream>#include <vector>#include <cmath>using namespace std;class LCA {private:
    int n, logN;
    vector<vector<int>> tree;
    vector<vector<int>> up;
    vector<int> depth;
    
    void dfs(int u, int parent) {
        up[u][0] = parent;
        for (int i = 1; i <= logN; i++) {
            up[u][i] = up[up[u][i-1]][i-1];
        }
        
        for (int v : tree[u]) {
            if (v != parent) {
                depth[v] = depth[u] + 1;
                dfs(v, u);
            }
        }
    }
    public:
    LCA(int n, int root) : n(n) {
        logN = log2(n) + 1;
        tree.resize(n + 1);
        up.resize(n + 1, vector<int>(logN + 1));
        depth.resize(n + 1, 0);
    }
    
    void addEdge(int u, int v) {
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    
    void build(int root) {
        depth[root] = 0;
        dfs(root, root);
    }
    
    int query(int u, int v) {
        if (depth[u] < depth[v]) {
            swap(u, v);
        }
        
        // 将u提到和v同一深度
        int diff = depth[u] - depth[v];
        for (int i = 0; i <= logN; i++) {
            if (diff & (1 << i)) {
                u = up[u][i];
            }
        }
        
        if (u == v) return u;
        
        // 同时向上跳
        for (int i = logN; i >= 0; i--) {
            if (up[u][i] != up[v][i]) {
                u = up[u][i];
                v = up[v][i];
            }
        }
        
        return up[u][0];
    }};int main() {
    int n, m, root;
    cin >> n >> m >> root;
    
    LCA lca(n, root);
    
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        lca.addEdge(u, v);
    }
    
    lca.build(root);
    
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        cout << lca.query(x, y) << endl;
    }
    
    return 0;}

• 转载请注明出处：英飞凌中国代理（官网）
• 本文地址：https://www.oliyun.com/algorithm/180.html