当前位置：首页 > article >正文

题目 3216 ⭐团建⭐【DFS】蓝桥杯2024年第十五届省赛

article 2025/3/6 22:57:38

小蓝正在和朋友们团建，有一个游戏项目需要两人合作，两个人分别拿到一棵大小为 n 和 m 的树，树上的每个结点上有一个正整数权值 $c_1, c_2, · · · , c_n$ , $d_1, d_2, · · · , d_m$ 。两个人需要从各自树的根结点 1 出发走向某个叶结点，从根到这个叶结点的路径上经过的所有结点上的权值构成了一个正整数序列，两人的序列的最长公共前缀即为他们的得分。给出两棵树，请计算两个人最多的得分是多少。

问题分析

输入：

两棵树的节点权值数组 c 和 d，分别表示第一棵树和第二棵树的节点权值。
树的节点编号从 1 到 n（或 m），根节点是 1。
树的结构通过邻接表表示。

目标：
从根节点到叶节点的路径中，找到两棵树路径序列的最长公共前缀（LCP）。

方法：

使用深度优先搜索（DFS）遍历两棵树，生成所有从根节点到叶节点的路径。
对于每对路径，计算它们的最长公共前缀。
找到所有路径对中的最大 LCP。

示例

// 示例输入
vector<int> c = {1, 2, 3, 4, 5, 6}; // 第一棵树的节点权值
vector<int> d = {1, 2, 3, 4, 7, 6}; // 第二棵树的节点权值

// 第一棵树的邻接表
vector<vector<int>> tree1 = {
    {},          // 节点 0（未使用）
    {2, 3},      // 节点 1 的子节点
    {4, 5},      // 节点 2 的子节点
    {6},         // 节点 3 的子节点
    {},          // 节点 4
    {},          // 节点 5
    {}           // 节点 6
};

// 第二棵树的邻接表
vector<vector<int>> tree2 = {
    {},          // 节点 0（未使用）
    {2, 3},      // 节点 1 的子节点
    {4, 7},      // 节点 2 的子节点
    {6},         // 节点 3 的子节点
    {},          // 节点 4
    {},          // 节点 5
    {},          // 节点 6
    {}           // 节点 7
};

解题思路

DFS 函数：
- 使用递归实现深度优先搜索，生成从根节点到叶节点的所有路径。
- 路径存储在 paths 中。
最长公共前缀函数：
- 比较两个路径序列的节点权值，找到最长公共前缀的长度。
最大得分函数：
- 生成两棵树的所有路径。
- 遍历所有路径对，计算它们的 LCP，并找到最大值。
主函数：
- 定义树的邻接表和节点权值数组。
- 调用 maxScore 函数计算最大得分。

C++实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 生成从根节点到叶节点的所有路径
void dfs(int node, vector<int>& path, vector<vector<int>>& paths, const vector<vector<int>>& tree) {
    path.push_back(node); // 将当前节点加入路径
    if (tree[node].empty()) { // 如果是叶节点
        paths.push_back(path); // 将当前路径加入结果
    } else {
        for (int child : tree[node]) { // 遍历子节点
            dfs(child, path, paths, tree);
        }
    }
    path.pop_back(); // 回溯
}

// 计算两个序列的最长公共前缀长度
int longestCommonPrefix(const vector<int>& seq1, const vector<int>& seq2, const vector<int>& c, const vector<int>& d) {
    int len = min(seq1.size(), seq2.size());
    for (int i = 0; i < len; i++) {
        if (c[seq1[i] - 1] != d[seq2[i] - 1]) { // 比较权值
            return i;
        }
    }
    return len;
}

// 计算最大得分
int maxScore(const vector<vector<int>>& tree1, const vector<vector<int>>& tree2, const vector<int>& c, const vector<int>& d) {
    // 生成第一棵树的所有路径
    vector<vector<int>> paths1;
    vector<int> path1;
    dfs(1, path1, paths1, tree1);

    // 生成第二棵树的所有路径
    vector<vector<int>> paths2;
    vector<int> path2;
    dfs(1, path2, paths2, tree2);

    // 计算所有路径对的最长公共前缀
    int maxLCP = 0;
    for (const auto& p1 : paths1) {
        for (const auto& p2 : paths2) {
            int lcp = longestCommonPrefix(p1, p2, c, d);
            maxLCP = max(maxLCP, lcp);
        }
    }

    return maxLCP;
}

复杂度分析

时间复杂度：
- 生成路径： $O (N + M)$ ，其中 $N$ 和 $M$ 分别是两棵树的节点数。
- 计算 LCP： $O(P _1×P_2 ×L)$ ，其中 $P_1$ 和 $P_2$ 是路径数，L 是路径的平均长度。
空间复杂度：
- 存储路径： $O(P_1 ×L+P_2 ×L)$ 。