Problem 4087 --D: 团建

4087: D: 团建

"
Time Limit $3$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $2$ 正确数量 $2$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

小蓝正在和朋友们团建,有一个游戏项目需要两人合作,两个人分别拿到 一棵大小为 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 之间的边。

输出一行包含一个整数表示答案。 
2 2
10 20
10 30
1 2
2 1
1

第一个样例 :

两个序列可以为 [10, 20] , [10, 30] ,最大前缀为 1 ;

第二个样例:

两个序列可以为 [10, 20, 40] , [10, 20, 30] ,最大前缀为 2 。

【评测用例规模与约定】 

对于 20% 的评测用例,1 ≤ n, m ≤ 500 ; 对于所有评测用例,1 ≤ n, m ≤ 2 × 105,1 ≤ ci , di ≤ 108 ,1 ≤ ui , vi ≤ n , 1 ≤ pi , qi ≤ m ,对于任意结点,其儿子结点的权重互不相同。

推荐代码 查看4087 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$10 $ms] wanger 1095919 2024-04-17 23:51:48
内存最少[$13116 $KB] wanger 1095919 2024-04-17 23:51:48
第一AC wanger 1095919 2024-04-17 23:51:48
第一挑战 wanger 1095919 2024-04-17 23:51:48

赛题来源/所属竞赛 第十五届蓝桥杯大赛软件赛省赛 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛