比赛 20241128 评测结果 AAAAAAAAAAAAEEEEEEEE
题目名称 猴猴的比赛 最终得分 60
用户昵称 yuanna 运行时间 2.913 s
代码语言 C++ 内存使用 15.70 MiB
提交时间 2024-11-28 10:59:37
显示代码纯文本
#include <iostream>
using namespace std;
int n=0,fa1[100001]={0},fa2[100001]={0},zhan[100001]={0},zn=0,num=0;
bool son1[100001]={0},son2[100001]={0},con[10001][10001]={0};
bool fl[10001][10001]={0};
void se1(int root)
{
 zn++;
 zhan[zn]=root;
 if(root!=1)
 se1(fa1[root]);
 else
  while(zn!=0)
  {
   for(int i=zn-1;i>0;i--)
    con[zhan[zn]][zhan[i]]=1;
   zhan[zn]=0;zn--;
  }
}
void se2(int root)
{
 zn++;
 zhan[zn]=root;
 if(root!=1)
 se2(fa2[root]);
 else
  while(zn!=0)
  {
   for(int i=zn-1;i>0;i--)
    if(con[zhan[zn]][zhan[i]]==1)
     {
      num=num-fl[zhan[zn]][zhan[i]]+1;
      fl[zhan[zn]][zhan[i]]=1;
     }
   zhan[zn]=0;zn--;
  }
}
int main()
{
 freopen("monkeyclim.in","r",stdin);
 freopen("monkeyclim.out","w",stdout);
 fa1[1]=1;fa2[1]=1;
 cin>>n;
 for(int i=1;i<n;i++)
 {
  int a,b;
  cin>>a>>b;
  if(fa1[a]!=0)
   fa1[b]=a,son1[a]=1;
  else
   fa1[a]=b,son1[b]=1;
 }
 for(int i=1;i<n;i++)
 {
  int a,b;
  cin>>a>>b;
  if(fa2[a]!=0)
   fa2[b]=a,son2[a]=1;
  else
   fa2[a]=b,son2[b]=1;
 }
 for(int i=1;i<=n;i++)
  if(son1[i]==0)
   se1(i);
 for(int i=1;i<=n;i++)
  if(son2[i]==0)
   se2(i);
 cout<<num;
 
 
}