题目描述
猴猴今天要和小伙伴猩猩比赛爬树，为了公平不碰撞，猴猴和猩猩需要在不同的树上攀爬。于是它们选了两颗节点数同为n的树，并将两棵树的节点分别以1~n标号（根节点标号为1），但两棵树的节点连接方式不尽相同。
现在它们决定选择两个标号的点进行比赛。为了方便统计，规定它们比赛中必须都向上爬。（即选定的赛段节点u→节点v都必须指向叶子方向）请你求出这两棵树上共有多少对节点满足比赛的需求。
题目解析
先求出第一棵树的
d
f
s
dfs
dfs序，得到每个节点本身的编号以及子树的编号范围
[
l
i
,
r
i
]
[l_i,r_i]
[li,ri] 。 用树状数组来维护后面的计算。 在
D
F
S
DFS
DFS处理第二棵树时，我们每处理完一个节点，就将该节点在第一棵树中的对应编号设为
1
1
1，处理完所有子节点后，查询编号区间
[
l
i
,
r
i
]
[l_i,r_i]
[li,ri]的区间和，即当前子树下，有多少个节点在树
1
1
1中也是当前节点的子孙节点。维护计数即可。
代码
#include<cstdio>
#include<cstring>
using namespace std
;
const int N
=100000+5;
int n
,cnt
,ls
[N
],next
[2*N
],v
[2*N
];
inline void add(int x
,int y
)
{
next
[++cnt
]=ls
[x
]; ls
[x
]=cnt
;v
[cnt
]=y
;
next
[++cnt
]=ls
[y
]; ls
[y
]=cnt
;v
[cnt
]=x
;
}
int id
,dfn
[N
],siz
[N
];
void pre(int x
,int fa
)
{
dfn
[x
]=++id
; siz
[x
]=1;
for(int i
=ls
[x
];i
;i
=next
[i
])
{
int y
=v
[i
];
if(y
==fa
) continue;
pre(y
,x
);
siz
[x
]+=siz
[y
];
}
}
int t
[N
],ans
[N
];
void change(int x
,int num
) {for(;x
<=n
;x
+=x
&-x
) t
[x
]+=num
;}
int ask(int x
) {int ret
=0;for(;x
;x
-=x
&-x
) ret
+=t
[x
];return ret
;}
void dfs(int x
,int fa
)
{
int cmp
=0;
for(int i
=ls
[x
];i
;i
=next
[i
])
{
int y
=v
[i
];
if(y
==fa
) continue;
cmp
=ask(dfn
[y
]+siz
[y
]-1)-ask(dfn
[y
]-1);
dfs(y
,x
);
ans
[y
]-=cmp
;
change(dfn
[y
],1);
}
ans
[x
]=ask(dfn
[x
]+siz
[x
]-1)-ask(dfn
[x
]-1);
}
int main()
{
int x
,y
; scanf("%d",&n
);
for(int i
=1;i
<n
;i
++) scanf("%d%d",&x
,&y
),add(x
,y
);
pre(1,0);
cnt
=0;memset(ls
,0,sizeof(ls
));
for(int i
=1;i
<n
;i
++) scanf("%d%d",&x
,&y
),add(x
,y
);
dfs(1,0);
for(int i
=1;i
<=n
;i
++) ans
[0]+=ans
[i
];
printf("%d",ans
[0]);
return 0;
}
