比赛 |
20241128 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
猴猴的比赛 |
最终得分 |
100 |
用户昵称 |
黄天乐 |
运行时间 |
2.655 s |
代码语言 |
C++ |
内存使用 |
13.89 MiB |
提交时间 |
2024-11-28 10:40:07 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int n;
int fa1[MAXN],fa2[MAXN];
priority_queue<int>q[MAXN],p[MAXN];
void find1(int x,int f){
if(x!=fa1[x]){
q[fa1[x]].push(f);
find1(fa1[x],f);
}else return ;
}
void find2(int x,int f){
if(x!=fa2[x]){
p[fa2[x]].push(f);
find2(fa2[x],f);
}else return ;
}
int ans;
int main(){
freopen("monkeyclim.in","r",stdin);
freopen("monkeyclim.out","w",stdout);
cin>>n;
for(int i=1;i<=n-1;i++){
fa1[i]=i;
fa2[i]=i;
}
for(int i=1;i<=n-1;i++){
int a,b;
cin>>a>>b;
if(a>b)swap(a,b);
fa1[b]=a;
}
for(int i=1;i<=n-1;i++){
int a,b;
cin>>a>>b;
if(a>b)swap(a,b);
fa2[b]=a;
}
for(int i=1;i<=n;i++){
find1(i,i);
find2(i,i);
}
for(int i=1;i<=n;i++){
while(!q[i].empty()&&!p[i].empty()){
int x=q[i].top();
int y=p[i].top();
if(x>y){
q[i].pop();
}else if(x<y){
p[i].pop();
}else {
ans++;
q[i].pop();
p[i].pop();
}
}
}
cout<<ans<<endl;
return 0;
}