由于要求边完全相同,所以在 A 中存在的边但 B 中不存在的一定会被删掉,其它边保留,连边就连 B 中剩下没连的。
所以,只用统计 A 中出现过的但 B 中没有出现过的边,对于一条边 ,如果
交换
,然后查询数对是否出现过即可。
用一个 map 维护。
#include<bits/stdc++.h>
#define re
using namespace std;
#define int long long
inline int read(){
re int t=0;re char v=getchar();
while(v<'0')v=getchar();
while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
return t;
}
map<int,int>v;
int n,ans;
signed main(){
n=read();
for(re int i=1,x,y;i<n;++i){
x=read(),y=read();
if(x>y)x^=y^=x^=y;
v[x*n+y]=1;
}
for(re int i=1,x,y;i<n;++i){
x=read(),y=read();
if(x>y)x^=y^=x^=y;
if(!v[x*n+y])++ans;
}
printf("%lld",ans);
}


京公网安备 11010502036488号