蓝桥杯2024年第十五届省赛真题-团建

解题思路:

dfs，也就是深度优先搜索

注意事项:

有一个测试样例是错的，输入内容如下：

4 2
49868141 62921933 1 1
49868141 62921933
1 2
3 1
1 2

可以看到这个测试样例缺少一行输入，故这段代码只能在这个判题平台上拿到91分。

参考代码:

#include <bits/stdc++.h>
#define int long long//其实上面那个样例好像是想卡longlong来着，没这句就会从“运行错误”变成“答案错误”。。。
using namespace std;

int ans = 0;//答案
vector<int> weight1, weight2;//两棵树的各节点权值
vector<vector<int>> adj1, adj2;//两棵树的邻接表，存储树的结构


//dfs函数。node1为第一个树的被搜索结点，node1parent为其父结点。depth是dfs搜索深度，adj1为树1邻接表，weight1为树1各结点权值。
int dfs(int node1, int node1parent, int node2, int node2parent, int depth, vector<vector<int>>& adj1, vector<vector<int>>& adj2, vector<int>& weight1, vector<int>& weight2)
{
    ans = max(ans, depth);//更新答案
    map<int, int>mp;//建立一个树1的，权值到节点的映射mp
    //遍历树1的node1结点的子节点
    for (const auto& n : adj1[node1])
    {
        if (n != node1parent)//排除父结点
        {
            mp[weight1[n]] = n;//联系权值与子结点
        }
    }
    //遍历树2的node2结点的子结点
    for (const auto& n : adj2[node2])
    {
        if (n != node2parent)//排除父结点
        {
            if (mp.count(weight2[n]) != 0)//如果在树1的node1的子节点中找到了和树2的node2的子节点权值相等的子结点，就继续递归dfs搜索下去
            {
                    //更新答案。其中，mp[weight2[n]]是与树2结点node2的子节点n相同权值的树1子节点。两个父节点则为现在所搜索的结点node1和node2。深度记得+1
                ans = max(ans, dfs(mp[weight2[n]], node1, n, node2, depth + 1, adj1, adj2, weight1, weight2));
            }
        }
    }
    return ans;
}

signed main()//一定是signed而不是int，因为我们上面的define把int定义为了longlong，而longlong不能作为返回值类型
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    weight1.resize(n+5);
    weight2.resize(m+5);
    adj1.resize(n + 10);
    adj2.resize(m + 10);
    for (int i = 1; i <= n; i++)
    {
        cin >> weight1[i];
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> weight2[i];
    }
    int u, v, p, q;
    for (int i = 1; i <= n - 1; i++)
    {
        cin >> u >> v;
        adj1[u].push_back(v);
        adj1[v].push_back(u);
    }
    for (int i = 1; i <= m - 1; i++)
    {
        cin >> p >> q;
        adj2[q].push_back(p);
        adj2[p].push_back(q);
    }
    if(weight1[1]!=weight2[1])//如果根节点不相同，说明最长共同前缀是0
    {
        cout << "0";
    }
    else
    {        //如果根节点相同则开始dfs搜索
        cout << dfs(1, 0, 1, 0, 1, adj1, adj2, weight1, weight2);
    }
    

}

以防你真的很想ac：我找到一段能在这个平台ac的代码，但我不知道为什么它能在这个平台ac。我在本地测试上面那个测试样例的时候也过不了，但它就是能ac。关键可能出现在主函数，但我不想去折腾了。

#include <bits/stdc++.h> 
#define int long long    
#define endl '\n'        
using namespace std;

int mmax = 0;  


int dfs(int fn, int pn, int fm, int pm, int dep, const vector<int>& c, const vector<int>& d, const vector<vector<int>>& G, const vector<vector<int>>& T) {
   

    mmax = max(mmax, dep);  

    map<int, int> mp;  
    for (auto t1 : G[fn]) { 
        if (t1 != pn) {     
            mp[c[t1]] = t1; /
        }
    }

   
    for (auto t2 : T[fm]) {
        if (t2 != pm) { 
            if (mp.count(d[t2]) != 0) {
                mmax = max(mmax, dfs(mp[d[t2]], fn, t2, fm, dep + 1, c, d, G, T));
            }
        }
    }

    return mmax; 
}

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

    int n, m;
    cin >> n >> m;  
    
    vector<int> weight1(n + 5), weight2(m + 5);  
    for (int i = 1; i <= n; i++) {
        cin >> weight1[i];  
    }
    for (int i = 1; i <= m; i++) {
        cin >> weight2[i];  
    }
    
    vector<vector<int>> tree1(n + 5), tree2(m + 5); 
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;  
        tree1[u].push_back(v);  
        tree1[v].push_back(u);
    }
    for (int i = 1; i < m; i++) {
        int u, v;
        cin >> u >> v;  
        tree2[u].push_back(v); 
        tree2[v].push_back(u);
    }
    if (weight1[1] != weight2[1]) {
        cout << 0 << endl;
    } else {
        int res = dfs(1, 0, 1, 0, 1, weight1, weight2, tree1, tree2);
        cout << res << endl;  
    }
    
    return 0;
}