首页 > 其他分享 >蓝桥杯2024年第十五届省赛A组-团建

蓝桥杯2024年第十五届省赛A组-团建

时间:2024-08-01 16:27:49浏览次数:15  
标签:2024 结点 前缀 10 int 蓝桥 mmax 权值 团建

题目描述

小蓝正在和朋友们团建,有一个游戏项目需要两人合作,两个人分别拿到一棵大小为 n 和 m 的树,树上的每个结点上有一个正整数权值。

两个人需要从各自树的根结点 1 出发走向某个叶结点,从根到这个叶结点的路径上经过的所有结点上的权值构成了一个正整数序列,两人的序列的最长公共前缀即为他们的得分。给出两棵树,请计算两个人最多的得分是多少。

输入格式

输入的第一行包含两个正整数 n, m ,用一个空格分隔。

第二行包含 n 个正整数 c1, c2, · · · , cn ,相邻整数之间使用一个空格分隔,其中 ci 表示第一棵树结点 i 上的权值。

第三行包含 m 个正整数 d1, d2, · · · , dm ,相邻整数之间使用一个空格分隔,其中 di 表示第二棵树结点 i 上的权值。

接下来 n − 1 行,每行包含两个正整数 ui, vi 表示第一棵树中包含一条 ui 和vi 之间的边。

接下来 m − 1 行,每行包含两个正整数 pi, qi 表示第二棵树中包含一条 pi 和 qi 之间的边。

输出格式

输出一行包含一个整数表示答案。

样例1输入

2 2
10 20
10 30
1 2
2 1

样例1输出

1

样例2输入

5 4
10 20 30 40 50
10 40 20 30
1 2
1 3
2 4
3 5
1 2
1 3
3 4

样例2输出

2

提示

【样例1说明】两个序列可以为 [10, 20] , [10, 30] ,最大前缀为 1 。

【样例2说明】两个序列可以为 [10, 20, 40] , [10, 20, 30] ,最大前缀为 2 。

【评测用例规模与约定】

对于 20% 的评测用例,1 ≤ n, m ≤ 500 。

对于所有评测用例,1 ≤ n, m ≤ 2 × 10^5,1 ≤ ci, di ≤ 10^8 ,1 ≤ ui, vi ≤ n ,1 ≤ pi, qi ≤ m ,对于任意结点,其子结点的权重互不相同。

整体思路

考虑深度优先搜索,从根结点开始,先构建一个从第一棵树子结点权值到边的映射,再遍历第二棵树的子结点,如果子结点的权值在第一棵树的映射中,则继续向下搜索。

#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)
{
    // fn是当前遍历的第一棵树的结点,pn是fn的父结点, fm是当前遍历的第二棵树的结点,pm是fm的父结点 
    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;
}

具体步骤

1. 读入数据,构建两棵树各结点的权值数组的边的邻接表。

2. 如果两棵树根结点的权值不同,则最长公共前缀的长度一定为0(为了提升效率,可以不进行特判)。

3. 对两棵树同时从根节点进行深度优先搜索(暴力求解两棵树的dfs会TLE),将当前结点的子结点信息存入哈希表(邻接表中有当前结点与父结点的边,需要特判避免,防止重复访问已经访问过的节点导致无限循环),如果当前遍历的两个结点具有相同的权值(传参时保证当前结点的权值相同),并且它们的子结点也存在匹配的公共前缀,那么dfs函数会继续递归地遍历这两个结点的子结点,遍历的同时不断更新最长公共前缀的长度mmax。

标签:2024,结点,前缀,10,int,蓝桥,mmax,权值,团建
From: https://blog.csdn.net/hehe_666888/article/details/140848198

相关文章

  • centos在线安装部署2024年最新的docker版本
    1.yum包更新到最新sudoyumupdate-y2.安装依赖软件包sudoyuminstall-yyum-utilsdevice-mapper-persistent-datalvm23.添加阿里的镜像,下载镜像速度比较快sudoyum-config-manager--add-repohttp://mirrors.aliyun.com/docker-ce/linux/centos/docker-c......
  • 【IEEE出版 | ICBASE 2020-2023 均已被 EI , Scopus检索 | 温州理工学院、加拿大圭尔
    第五届大数据、人工智能与软件工程国际研讨会(ICBASE2024)将于2024年09月20-22日在中国温州隆重举行。会议主要围绕大数据、人工智能与软件工程等研究领域展开讨论。会议旨在为从事大数据、人工智能与软件工程研究的专家学者、工程技术人员、技术研发人员提供一个共享科研成果和......
  • 2024 CT02 模拟赛
    \(\text{Contest1}\)\(\text{HeavenlyAltitudes}\)\(\text{description}\)给你一个集合\(S=\{1,2,...,n\}\),要求分成\(m\)段,段之间不考虑顺序,段中的元素不考虑顺序,现给你每段的最小值\(a_1,a_2,...,a_m\),求有多少种合法的划分方式,答案对\(10^9+7\)取模。\(1......
  • 【笔记】字符串选讲 2024.8.1
    [COCI2015-2016#5]OOP(Trie)P6727[COCI2015-2016#5]OOP-洛谷|计算机科学教育新生态(luogu.com.cn)正反串分别建Trie,可以搞出两个dfn区间,加之长度限制,三维数点。有\(O(n\logn)\)做法。将字典串\(S[1..m]\),对所有\(1\leqi\leqm\),将\(S[i+1,m]\)的hash值插入......
  • 三年级上册英语人教版电子课本新版pdf+mp3音频课件免费下载2024秋季版
    2024年秋季新版三年级上册英语人教版课件及mp3音频免费下载:新版英语PDF电子课本预览:虽然自己是老师,但不出意外的话今年应该不会教三年级。but女儿9月读三年级,并且我们在不同的学校。所以咬咬牙还是把三年级的英语给备了,自己先学会才能更好的教女儿念。由于今年是2024版新教材,......
  • 努力努力努力的第十四天(2024.7.31)
    昨天日期写错了写成2020.7.30,应该是2024.7.31(手滑了哈哈哈)1.行列转换效果演示:这是未经行列转换操作的t_score表:这是经过行列转换后的t_score表:第一步:确定初步的做法使用分组查询(groupby)能够将单个学生的成绩依次查询出来,再加上三列查询(分别定义成'语文''数学''......
  • Gartner 魔力象限:安全信息和事件管理 (SIEM) 2024
    GartnerMagicQuadrantforSecurityInformationandEventManagement2024Gartner魔力象限:安全信息和事件管理2024请访问原文链接:https://sysin.org/blog/gartner-magic-quadrant-siem-2024/,查看最新版。原创作品,转载请保留出处。Gartner魔力象限:安全信息和事件管理202......
  • Metasploit Pro 4.22.2-2024072501 (Linux, Windows) - 专业渗透测试框架
    MetasploitPro4.22.2-2024072501(Linux,Windows)-专业渗透测试框架Rapid7Penetrationtesting,releaseJul25,2024请访问原文链接:https://sysin.org/blog/metasploit-pro-4/,查看最新版。原创作品,转载请保留出处。世界上最广泛使用的渗透测试框架知识就是力量,尤其是......
  • 2024零基础·短视频图文带货实战课:0基础从破圈到爆单实操(35节课)
    课程大纲老号如何转型?新号如何搭建?如何做账号定位?如何选品?如何创作短视频图文?如何出单?适用人群想要学习短视频图文带货的小伙伴想要了解短视频图文成功核心玩法想要掌握智能AI剪辑短视频和图文的技巧课程目录00.学前必读mov.mp401.新号如何搭建账户?mov.mp402......
  • 【办公类-53-03】2024年第一学期校历制作(“月/日(星期)”版、排班表、跳过节日和周三)
    背景需求:前期代码制作出2024年第一学期校历,按照5天一周的方法,提取实际工作日。制作成“周计划教案”使用的长日期、短日期-【办公类-53--01】2024年第一学期校历制作(星火讯飞提取实际工作日,5天一行)-CSDN博客文章浏览阅读489次,点赞19次,收藏5次。-【办公类-53--01】2024年第一......