2024蓝桥A组D题

问题描述

格式输入

输入的第一行包含两个正整数n,m，用一个空格分隔。
第二行包含n个正整数c1,c2,··· ,cn，相邻整数之间使用一个空格分隔，
其中ci表示第一棵树结点i上的权值。
第三行包含m个正整数d1,d2,··· ,dm，相邻整数之间使用一个空格分隔，
其中di表示第二棵树结点i上的权值。
接下来n−1行，每行包含两个正整数ui,vi表示第一棵树中包含一条ui和
vi之间的边。
接下来m−1行，每行包含两个正整数pi,qi表示第二棵树中包含一条pi
和qi之间的边。

格式输出

输出一行包含一个整数表示答案。

样例输入

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

评测用例规模与约定

对于20%的评测用例，1≤n,m≤500；
对于所有评测用例，1≤n,m≤2×10^5，1≤ci,di ≤10^8，1≤ui,vi ≤n，
1≤pi,qi≤m，对于任意结点，其儿子结点的权重互不相同

解析

dfs遍历树的同时，用map来记录在n树中出现过的节点和权值，同时看m树是否有相同的对应，有就dfs下去，取得最大值再加根节点本身1个。

参考程序

#include<bits/stdc++.h>
using namespace std;
const int N=200020;
int c[N],d[N];
vector<int>e[N],f[N];
int dp[N];
void dfs(int x,int y,int p,int q)
{
    map<int,int>mp;
    for(int i=0;i<e[x].size();i++)
    {
        int nx=e[x][i];
        if(nx==p)continue;
        mp[c[nx]]=nx;
    }
    int mx=0;
    for(int i=0;i<f[y].size();i++)
    {
        int ny=f[y][i];
        if(ny==q)continue;
        if(mp.count(d[ny]))
        {
            dfs(mp[d[ny]],ny,x,y);
            mx=max(mx,dp[ny]);
        }
    }
    dp[y]=mx+1;
}
int main()
{
    int n,m;
    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 u,v;cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for(int i=1;i<m;i++)
    {
        int p,q;cin>>p>>q;
        f[p].push_back(q);
        f[q].push_back(p);
    }
    if(c[1]!=d[1])
    {cout<<0;return 0;}
    dfs(1,1,0,0);
    cout<<dp[1];
    return 0;
}

难度等级

⭐️⭐️⭐️⭐️⭐️（1~10星）

以个人刷题整理为目的，如若侵权，请联系删除~