该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给出两棵以节点 1 为根、共有 n 个节点的树 T₁、T₂。
请统计有多少对点对 \((a,b)\)（满足 \(1\le a<b\le n\)），使它们在两棵树上的最近公共祖先（LCA）相同。

输入格式

T
（以下内容重复 T 组）
  n
  （T₁ 的 n−1 条边）
  x₁ y₁
  x₂ y₂
  ⋮
  x_{n−1} y_{n−1}
  （T₂ 的 n−1 条边）
  u₁ v₁
  u₂ v₂
  ⋮
  u_{n−1} v_{n−1}

• 第一行一个正整数 T，表示数据组数。
• 对于每组数据：
  • 首行一个正整数 n（节点数）。
  • 接下来 n−1 行，每行两个整数 x y，表示树 T₁ 中有一条边 (x, y)。
  • 再接下来 n−1 行，每行两个整数 u v，表示树 T₂ 中有一条边 (u, v)。
• 两棵树都以 1 为根，节点编号均为 1…n。

输出格式

对于每组数据，输出一行一个整数，表示满足条件的点对数目。

1
7
1 2
1 3
2 4
2 5
3 6
3 7
1 2
1 4
2 5
2 3
4 6
4 7

12

数据范围与提示

• 对于全部数据，\(1\le T\le 3\)。
• 建议用树形差分、哈希或 DC 分治 等方法实现 \(O(n\log n)\) 或更优复杂度。