算法1

(暴力枚举) $O(n^2)$

采用邻接矩阵存储树，额外开两个数组记录路径。DFS遍历寻找判断即可。

C++ 代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<map>
#include<set>
using namespace std;
typedef long long int ll;
const int INF=1e16;

int n,m;
int c[200005],d[200005];
vector<vector<int>> v1(200005);
vector<vector<int>> v2(200005);
vector<int> r1(200005,0);
vector<int> r2(200005,0);
int maxcnt=0;

void dfs(int t1,int t2,int cnt){
    if(cnt>maxcnt){
        maxcnt=cnt;
    }
    //cout << "1" << "\n";
    for(int i=0;i<v1[t1].size();i++){
        for(int j=0;j<v2[t2].size();j++){
            if(r1[v1[t1][i]]!=1 && r2[v2[t2][j]]!=1 && c[v1[t1][i]]==d[v2[t2][j]]){
                r1[v1[t1][i]]=1;r2[v2[t2][j]]=1;
                dfs(v1[t1][i],v2[t2][j],cnt+1);
                r1[v1[t1][i]]=0;r2[v2[t2][j]]=0;
            }
        }
    }
}

void solve(){
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> c[i];
    }
    for(int i=1;i<=m;i++){
        cin >> d[i];
    }
    for(int i=1;i<n;i++){
        int x,y;
        cin >> x >> y;
        v1[x].push_back(y);
        v1[y].push_back(x);
    }
    for(int i=1;i<m;i++){
        int x,y;
        cin >> x >> y;
        v2[x].push_back(y);
        v2[y].push_back(x);
    }
    if(c[1]!=d[1]){
        cout << 0;
        return;
    }
    r1[1]=1;
    r2[1]=1;
    dfs(1,1,1);
    cout <<maxcnt;
}

int main(){
    solve();
}