比赛 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;
}