题解：P10388 [蓝桥杯 2024 省 A] 团建

happy_lazier · 2025-04-10 12:41:39 · 题解

题目大意：在两棵树上分别找到一条路径使公共前缀最大。那么可以考虑把其中一棵树制作成类似于字典树的形式，但是值域有点大，所以对于字典树的节点考虑用 map 记录，之后就是在另一棵树上遍历去更新答案了，代码如下

#define  _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include<cstdio>
#include<random>
#include<cstdlib>
#include<algorithm>
#include<array>
#include<chrono>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> PII;
#define fi first
#define sc second
#define inf 0x3f3f3f3f3f
#define all(x) x.begin(),x.end()
#define YES cout<<"YES"<<'\n';
#define NO cout<<"NO"<<'\n';
#define Yes cout<<"Yes"<<'\n';
#define No cout<<"No"<<'\n';
#define rep(i, l, r) for (ll i = (l); i <= (r); ++i)
#define rep_(i, l, r) for (ll i = (l); i >= (r); --i)
using namespace std;
std::mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());//ull x=rng()
const ll P = 1e9 + 7;
const ll Inf = 2e18;
const ll M = 1e5 + 7;
const ll N = 2e5 + 7;
const int dx[5] = { 0,1,0,-1,0 }, dy[5] = { 1,0,-1,0,0 };
const double eps = 1e-6;
long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}
long long qmin(long long a, long long b) {
    long long res = 1;
    a %= P;
    while (b) {
        if (b & 1)res = res * a % P;
        b >>= 1;
        a = a * a % P;
    }
    return res;
}
long long inv(long long x) {
    return qmin(x, P - 2);
}
inline ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch>'9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar(), x %= P;
    return x * f;
}
//char* p1, * p2, buf[1 << 20];
//inline char gc() { if (p1 == p2)p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin); return p1 == p2 ? ' ' : *p1++; }
//inline long long read() {
//    register long long s = 0; register char c = gc();
//    while (c < '0' || c>'9') c = gc();
//    while (c >= '0' && c <= '9') s = (s << 3) + (s << 1) + (c ^ 48), c = gc();
//    return s;
//}
ll lowbit(ll x) {
    return x & (-x);
}
struct fenwick {
    vector<int>tr;
    int n;
    fenwick(int mx = 0) {
        n = mx;
        tr.assign(n + 10, 0);
    }
    void init(int mx) {
        n = mx;
        tr.assign(n + 10, 0);
    }
    void add(int x, int v) {
        for (int i = x; i <= n; i += i & (-i)) {
            tr[i] += v;
        }
    }
    int sum(int x) {
        int ans = 0;
        for (int i = x; i; i -= i & (-i)) {
            ans += tr[i];
        }
        return ans;
    }
    int rangeSum(int l, int r) {
        return sum(r) - sum(l - 1);
    }
};
int c[N], d[N];
vector<int>g1[N], g2[N];
map<int, int>mp[N];
int cnt;
void dfs(int u, int v, int rt) {
    for (auto x : g1[u]) {
        if (x == v)continue;
        if (!mp[rt].count(c[x])) {
            mp[rt][c[x]] = ++cnt;
        }
        dfs(x, u, mp[rt][c[x]]);
    }
}
int dfs2(int u, int v, int dep, int rt) {
    int ans = dep;
    for (auto x : g2[u]) {
        if (x == v)continue;
        if (mp[rt].count(d[x])) {
            ans = max(ans, dfs2(x, u, dep + 1, mp[rt][d[x]]));
        }
    }
    return ans;
}
void solve() {
    int n, m;
    cnt = 0;
    cin >> n >> m;
    rep(i, 1, n)cin >> c[i];
    rep(i, 1, m)cin >> d[i];
    int u, v;
    rep(i, 2, n) {
        cin >> u >> v;
        g1[u].push_back(v);
        g1[v].push_back(u);
    }
    rep(i, 2, m) {
        cin >> u >> v;
        g2[u].push_back(v);
        g2[v].push_back(u);
    }
    int ans = 0;
    dfs(1, 0, 0);
    if (d[1] != c[1]) {
        cout << 0;
        return;
    }
    ans = dfs2(1, 0, 1, 0);
    cout << ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    //cout << fixed << setprecision(3);
    //cin >> t;
    //t = read();
    while (t--) solve();
    return 0;
}