「Test」猴猴的比赛

题意：有两棵节点数同为 $n$ 的数，编号都为 $1\sim n$，现在问你两棵树中编号为 $(u,v)$ 且都是从上到下的方向的点对有多少个。

解析：很明显 $(u,v)$ 为从上到下的方向，那么 $v$ 肯定在 $u$ 的子树中。

如何判断是否在子树中呢？dfs 序！！！

于是首先把第一棵树的 dfs 序求出来，然后以 dfs 序为下标建立一个树状数组，开始遍历第二棵树。我们统计 $(u,v)$ 中 $v$ 的数量，那么要满足 $v$ 在 $u$ 的子树中，遍历到 $v$ 时，小于 $dfn[v]$ ($v$ 的 dfs 序) 的数量即为在第一棵树中有多少个点是 $v$ 的上层节点，这点可以通过树状数组求和做到。但求和不仅要满足 $v$ 在第一棵树的子树中，还要再第二棵树的子树中，所以我们对于第二棵树已经遍历的点，把它们的子树在树状数组中加 $1$，这样求和时才能满足只有同时在两棵树中的点被算了贡献。

最后把每个点的求和值加起来即可。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define INF 1e9
using namespace std;
const int maxn=100101;
int n,dfn1[maxn],dfn2[maxn],tot,tree[maxn];
int head1[maxn],cnt1,head2[maxn],cnt2;
int s[maxn],ans;
struct node
{
	int next;
	int to;
}e1[maxn<<1],e2[maxn<<1];
void add1(int from,int to)
{
	e1[++cnt1].next=head1[from];
	e1[cnt1].to=to;
	head1[from]=cnt1;
}
void add2(int from,int to)
{
	e2[++cnt2].next=head2[from];
	e2[cnt2].to=to;
	head2[from]=cnt2;
}
void dfs1(int u,int fa)
{
	dfn1[u]=++tot;
	for(int i=head1[u];i;i=e1[i].next)
	{
		int v=e1[i].to;
		if(v==fa)
			continue;
		dfs1(v,u);
	}
	dfn2[u]=tot;
}
int lowbit(int x)
{
	return x&(-x);
}
void add(int x,int val)
{
	for(int i=x;i<=n;i+=lowbit(i))
		tree[i]+=val;
}
int query(int x)
{
	int sum=0;
	for(int i=x;i;i-=lowbit(i))
		sum+=tree[i];
	return sum;
}
void dfs2(int u,int fa)
{
	s[u]=query(dfn1[u]-1);//计算答案
	add(dfn1[u],1);// 对访问过的点加贡献
	add(dfn2[u],-1);
	for(int i=head2[u];i;i=e2[i].next)
	{
		int v=e2[i].to;
		if(v==fa)
			continue;
		dfs2(v,u);
	}
	add(dfn1[u],-1);
	add(dfn2[u],1);//访问完，清除贡献
}
int main()
{
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add1(a,b);
		add1(b,a);
	}
	for(int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add2(a,b);
		add2(b,a);
	}
	dfs1(1,0);
	dfs2(1,0);
	for(int i=1;i<=n;i++)
		ans+=s[i];
	printf("%d",ans);
	return 0;
}