题目大意：
题目链接：https://www.51nod.com/Contest/Problem.html#contestProblemId=1150 猴猴今天要和小伙伴猩猩比赛爬树，为了公平不碰撞，猴猴和猩猩需要在不同的树上攀爬。于是它们选了两颗节点数同为n的树，并将两棵树的节点分别以1~n标号（根节点标号为1），但两棵树的节点连接方式不尽相同。
现在它们决定选择两个标号的点进行比赛。为了方便统计，规定它们比赛中必须都向上爬。（即选定的赛段节点u→节点v都必须指向叶子方向）请你求出这两棵树上共有多少对节点满足比赛的需求。
思路：
我们对第一棵树的每一个节点按
d
f
s
dfs
dfs序标号。然后顺便求出每一个节点为根的子树的编号区间
[
L
x
,
R
x
]
[L_x,R_x]
[Lx,Rx]。 然后对第二棵树进行
d
f
s
dfs
dfs。对于一个点
x
x
x，我们先将他的所有子节点求出答案，每求完一个点的答案就把这个点在第一棵树中对应的编号位置
a
i
a_i
ai记为1。那么
x
x
x与其子节点对答案的贡献就是
∑
i
=
L
x
R
x
a
i
\sum^{R_x}_{i=L_x}a_i
∑i=LxRxai。 时间复杂度
O
(
n
log
n
)
O(n\log n)
O(nlogn)
代码：
#include <cstdio>
#include <cstring>
using namespace std
;
const int N
=100010;
int n
,tot
,head
[N
],L
[N
],R
[N
];
long long ans
;
struct edge
{
int next
,to
;
}e
[N
*2];
struct BIT
{
int c
[N
];
void add(int x
)
{
for (int i
=x
;i
<=n
;i
+=i
&-i
)
c
[i
]++;
}
int ask(int x
)
{
int sum
=0;
for (int i
=x
;i
;i
-=i
&-i
)
sum
+=c
[i
];
return sum
;
}
}bit
;
void add(int from
,int to
)
{
e
[++tot
].to
=to
;
e
[tot
].next
=head
[from
];
head
[from
]=tot
;
}
void dfs1(int x
,int fa
)
{
L
[x
]=++tot
;
for (int i
=head
[x
];~i
;i
=e
[i
].next
)
if (e
[i
].to
!=fa
) dfs1(e
[i
].to
,x
);
R
[x
]=tot
;
}
void dfs2(int x
,int fa
)
{
for (int i
=head
[x
];~i
;i
=e
[i
].next
)
if (e
[i
].to
!=fa
)
{
ans
-=(long long)bit
.ask(R
[e
[i
].to
])-bit
.ask(L
[e
[i
].to
]);
dfs2(e
[i
].to
,x
);
}
ans
+=(long long)bit
.ask(R
[x
])-bit
.ask(L
[x
]);
bit
.add(L
[x
]);
}
int main()
{
scanf("%d",&n
);
memset(head
,-1,sizeof(head
));
for (int i
=1,x
,y
;i
<n
;i
++)
{
scanf("%d%d",&x
,&y
);
add(x
,y
); add(y
,x
);
}
tot
=0; dfs1(1,0); tot
=0;
memset(head
,-1,sizeof(head
));
for (int i
=1,x
,y
;i
<n
;i
++)
{
scanf("%d%d",&x
,&y
);
add(x
,y
); add(y
,x
);
}
dfs2(1,0);
printf("%lld\n",ans
);
return 0;
}
