团建 蓝桥杯省a 15

问题描述

小蓝正在和朋友们团建，有一个游戏项目需要两人合作，两个人分别拿到一棵大小为 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 ，对于任意结点，其儿子结点的权重互不相同。

运行限制

总通过次数: 412  |  总提交次数: 536  |  通过率: 76.9%

难度: 中等   标签: 哈希表, 省赛, DFS, 2024

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m;
map<int, vector<int>> t1, t2;
int a[N], b[N];
vector<int> 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;
}