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