[10.27模拟赛]T3

Description

猴猴今天要和小伙伴猩猩比赛爬树，为了公平不碰撞，猴猴和猩猩需要在不同的树上攀爬。
于是它们选了两颗节点数同为\(n\)的树，并将两棵树的节点分别以\(1\)~\(n\)标号（根节点标号为\(1\)），但两棵树的节点连接方式不尽相同。
现在它们决定选择两个标号的点进行比赛。
为了方便统计，规定它们比赛中必须都向上爬。（即选定的赛段节点\(u→\)节点\(v\)都必须指向叶子方向）
请你求出这两棵树上共有多少对节点满足比赛的需求。

Input

第一行一个数\(n\)。\(（n≤100000）\)
接下来\(n-1\)行，每行\(2\)个数\(a\)和\(b\)，表示第一棵树\(a\)和\(b\)有树枝相连。
接下来\(n-1\)行，每行\(2\)个数\(a\)和\(b\)，表示第二棵树\(a\)和\(b\)有树枝相连。

Output

输出满足条件的对数。

Sample Input

4
1 2
2 3
3 4
1 2
2 3
2 4

Sample Output

5

Data Constraint

对于\(30\)%的数据：\(n≤1000\)
对于\(50\)%的数据：\(n≤10000\)
对于\(100\)%的数据：\(n≤100000\)，\(1≤a\),\(b≤n\)

Solution

Code

[10.27模拟赛]T3

原文：https://www.cnblogs.com/Agakiss/p/11779261.html