当前位置：首页 > news >正文

打卡信奥刷题（3442）用C++实现信奥题 P10388 [蓝桥杯 2024 省 A] 团建

news 2026/7/13 14:48:57

P10388 [蓝桥杯 2024 省 A] 团建

题目描述

小蓝正在和朋友们团建，有一个游戏项目需要两人合作，两个人分别拿到一棵大小为nnn和mmm的树，树上的每个结点上有一个正整数权值。
两个人需要从各自树的根结点111出发走向某个叶结点，从根到这个叶结点的路径上经过的所有结点上的权值构成了一个正整数序列，两人的序列的最长公共前缀即为他们的得分。给出两棵树，请计算两个人最多的得分是多少。

输入格式

输入的第一行包含两个正整数 $n, m $，用一个空格分隔。
第二行包含nnn个正整数 $c_1, c_2,\cdots , c_n $，相邻整数之间使用一个空格分隔，其中cic_ici表示第一棵树结点iii上的权值。
第三行包含mmm个正整数d1,d2,⋯ ,dmd_1, d_2,\cdots, d_md1,d2,⋯,dm，相邻整数之间使用一个空格分隔，其中did_idi表示第二棵树结点iii上的权值。
接下来n−1n - 1n−1行，每行包含两个正整数ui,viu_i , v_iui,vi表示第一棵树中包含一条uiu_iui和
viv_ivi之间的边。
接下来m−1m - 1m−1行，每行包含两个正整数pi,qip_i , q_ipi,qi表示第二棵树中包含一条pip_ipi
和qiq_iqi之间的边。

输出格式

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

输入输出样例 #1

输入 #1

2 2 10 20 10 30 1 2 2 1

输出 #1

输入输出样例 #2

输入 #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

说明/提示

对于20%20\%20%的评测用例，$1 ≤ n, m ≤ 500 $；
对于所有评测用例，$1 ≤ n, m ≤ 2 × 10^5，1 ≤ c_i
, d_i ≤ 10^8 ，1 ≤ u_i
, v_i ≤ n ，
1 ≤ p_i
, q_i ≤ m $，对于任意结点，其儿子结点的权重互不相同。

C++实现

#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intc[200005],d[200005];unordered_map<int,int>trie[200005];vector<int>G[200005],T[200005];voidinit(intx=1,intfa=0){for(autov:G[x]){if(v==fa)continue;trie[x][c[v]]=v;init(v,x);}}intsolve(intx=1,intfa=0,intget=1){intans=0;for(autov:T[x]){if(v==fa)continue;if(trie[get][d[v]])ans=max(ans,solve(v,x,trie[get][d[v]])+1);}returnans;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intn,m,u,v;cin>>n>>m;for(inti=1;i<=n;i++)cin>>c[i];for(inti=1;i<=m;i++)cin>>d[i];for(inti=1;i<n;i++){cin>>u>>v;G[u].push_back(v);G[v].push_back(u);}for(inti=1;i<m;i++){cin>>u>>v;T[u].push_back(v);T[v].push_back(u);}init();if(c[1]==d[1])cout<<solve()+1;elsecout<<0;return0;}