比赛 |
树状数组练习 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
猴猴的比赛 |
最终得分 |
100 |
用户昵称 |
zjzhe |
运行时间 |
1.453 s |
代码语言 |
C++ |
内存使用 |
10.87 MiB |
提交时间 |
2025-06-12 15:54:20 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,val[N],dfn[N],low[N],dn,ans;
vector<int>lk[N],lk2[N];
void add(int x,int v){for(;x<=n;x+=x&-x)val[x]+=v;}
int query(int x){
int res=0;
for(;x;x-=x&-x)res+=val[x];
return res;
}
void dfs2(int u,int f){
dfn[u]=++dn;
for(int v:lk2[u]){
if(v==f)continue;
dfs2(v,u);
}
low[u]=dn;
}
void dfs(int u,int f){
for(int v:lk[u]){
if(v==f)continue;
ans-=query(low[v])-query(dfn[v]-1);
dfs(v,u);
ans+=query(low[v])-query(dfn[v]-1);
}
add(dfn[u],1);
}
int main(){
freopen("monkeyclim.in","r",stdin);
freopen("monkeyclim.out","w",stdout);
cin>>n;
for(int i=1,a,b;i<n;i++)cin>>a>>b,lk[a].push_back(b),lk[b].push_back(a);
for(int i=1,a,b;i<n;i++)cin>>a>>b,lk2[a].push_back(b),lk2[b].push_back(a);
dfs2(1,0),dfs(1,0);
cout<<ans;
return 0;
}