問題描述

小藍(lán)正在和朋友們團(tuán)建，有一個(gè)游戲項(xiàng)目需要兩人合作，兩個(gè)人分別拿到一棵大小為?nn?和?mm?的樹，樹上的每個(gè)結(jié)點(diǎn)上有一個(gè)正整數(shù)權(quán)值。

兩個(gè)人需要從各自樹的根結(jié)點(diǎn) 1 出發(fā)走向某個(gè)葉結(jié)點(diǎn)，從根到這個(gè)葉結(jié)點(diǎn)的路徑上經(jīng)過的所有結(jié)點(diǎn)上的權(quán)值構(gòu)成了一個(gè)正整數(shù)序列，兩人的序列的最長公共前綴即為他們的得分。給出兩棵樹，請(qǐng)計(jì)算兩個(gè)人最多的得分是多少。

輸入格式

輸入的第一行包含兩個(gè)正整數(shù)?n,mn,m，用一個(gè)空格分隔。

第二行包含?nn?個(gè)正整數(shù)?c1,c2,??,cnc1?,c2?,?,cn?，相鄰整數(shù)之間使用一個(gè)空格分隔, 其中?cici??表示第一棵樹結(jié)點(diǎn)?ii?上的權(quán)值。

第三行包含?mm?個(gè)正整數(shù)?d1,d2,??,dmd1?,d2?,?,dm?，相鄰整數(shù)之間使用一個(gè)空格分隔，其中?didi??表示第二棵樹結(jié)點(diǎn)?ii?上的權(quán)值。

接下來?n?1n?1?行，每行包含兩個(gè)正整數(shù)?ui,viui?,vi??表示第一棵樹中包含一條?uiui??和?vivi??之間的邊。

接下來?m?1m?1?行，每行包含兩個(gè)正整數(shù)?pi,qipi?,qi??表示第二棵樹中包含一條?pipi??和?qiqi??之間的邊。

輸出格式

輸出一行包含一個(gè)整數(shù)表示答案。

樣例輸入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

樣例說明

在第一個(gè)樣例中，兩個(gè)序列可以為?[10,20],[10,30][10,20],[10,30]?，最大前綴為?11;

在第二個(gè)樣例中，兩個(gè)序列可以為?[10,20,40],[10,20,30][10,20,40],[10,20,30]?，最大前綴為?22。

評(píng)測用例規(guī)模與約定

對(duì)于?20%20%?的評(píng)測用例，?1≤n,m≤5001≤n,m≤500?;

對(duì)于所有評(píng)測用例，?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?，對(duì)于任意結(jié)點(diǎn)，其兒子結(jié)點(diǎn)的權(quán)重互不相同。

運(yùn)行限制

語言	最大運(yùn)行時(shí)間	最大運(yùn)行內(nèi)存
C++	3s	256M
C	3s	256M
Java	3s	512M
Python3	10s	1024M
PyPy3	3s	1024M
Go	5s	512M
JavaScript	5s	512M

總通過次數(shù): 412??|??總提交次數(shù): 536??|??通過率: 76.9%

難度: 中等???標(biāo)簽: 哈希表, 省賽, 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;
}