动效网站,天津票网网站,如何建立自己免费网站,项目计划书范文免费问题描述
小蓝正在和朋友们团建#xff0c;有一个游戏项目需要两人合作#xff0c;两个人分别拿到一棵大小为 nn 和 mm 的树#xff0c;树上的每个结点上有一个正整数权值。
两个人需要从各自树的根结点 1 出发走向某个叶结点#xff0c;从根到这个叶结点的路径上经过的所…问题描述
小蓝正在和朋友们团建有一个游戏项目需要两人合作两个人分别拿到一棵大小为 nn 和 mm 的树树上的每个结点上有一个正整数权值。
两个人需要从各自树的根结点 1 出发走向某个叶结点从根到这个叶结点的路径上经过的所有结点上的权值构成了一个正整数序列两人的序列的最长公共前缀即为他们的得分。给出两棵树请计算两个人最多的得分是多少。
输入格式
输入的第一行包含两个正整数 n,mn,m用一个空格分隔。
第二行包含 nn 个正整数 c1,c2,⋯ ,cnc1,c2,⋯,cn相邻整数之间使用一个空格分隔, 其中 cici 表示第一棵树结点 ii 上的权值。
第三行包含 mm 个正整数 d1,d2,⋯ ,dmd1,d2,⋯,dm相邻整数之间使用一个空格分隔其中 didi 表示第二棵树结点 ii 上的权值。
接下来 n−1n−1 行每行包含两个正整数 ui,viui,vi 表示第一棵树中包含一条 uiui 和 vivi 之间的边。
接下来 m−1m−1 行每行包含两个正整数 pi,qipi,qi 表示第二棵树中包含一条 pipi 和 qiqi 之间的边。
输出格式
输出一行包含一个整数表示答案。
样例输入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样例说明
在第一个样例中两个序列可以为 [10,20],[10,30][10,20],[10,30] 最大前缀为 11;
在第二个样例中两个序列可以为 [10,20,40],[10,20,30][10,20,40],[10,20,30] 最大前缀为 22。
评测用例规模与约定
对于 20%20% 的评测用例 1≤n,m≤5001≤n,m≤500 ;
对于所有评测用例 1≤n,m≤2×105,1≤ci,di≤108,1≤ui,vi≤n1≤n,m≤2×105,1≤ci,di≤108,1≤ui,vi≤n , 1≤pi,qi≤m1≤pi,qi≤m 对于任意结点其儿子结点的权重互不相同。
运行限制
语言最大运行时间最大运行内存C3s256MC3s256MJava3s512MPython310s1024MPyPy33s1024MGo5s512MJavaScript5s512M
总通过次数: 412 | 总提交次数: 536 | 通过率: 76.9%
难度: 中等 标签: 哈希表, 省赛, DFS, 2024
#include bits/stdc.h
using namespace std;
const int N 2e5 10;
int n, m;
mapint, vectorint t1, t2;
int a[N], b[N];
vectorint res;
int ans;
void dfs(int x, int y, int fx, int fy, int cnt)
{if(a[x] ! b[y]) return;
// res.push_back(a[x]);ans max(ans, cnt);for(int i 0; i t1[x].size(); i){if(t1[x][i] fx ) continue;for(int j 0; j t2[y].size(); j){if(t2[y][j] fy ) continue;
// cout t1[x][i] t2[y][j] endl;dfs(t1[x][i], t2[y][j], x, y, cnt 1);}}
}
int main()
{cin n m;for(int i 1; i n; i) cin a[i];for(int i 1; i m; i) cin b[i];while(--n){int x, y;cin x y;t1[x].push_back(y);t1[y].push_back(x);}while(--m){int x, y;cin x y;t2[x].push_back(y);t2[y].push_back(x);}dfs(1, 1, -1, -1, 1);cout ans;
// for(auto it : res)
// cout it endl;
}
