1007. 另一个 shu 论问题

题目描述

随着对算法竞赛研究的不断深入，河灵逐渐对“数论”与“树论”产生了浓厚的兴趣。现在，河灵有一棵包含 n 个节点的树，节点编号为 1 ∼ n，根节点为

1。我们记 gcd(x, y) 表示整数 x, y 的最大公约数，记 lca(x, y) 表示节点

x, y 在这棵树中的最近公共祖先的编号。河灵想知道，“数论”和“树论”碰撞在一起，会产生什么样的火花？所以河灵想请你求出，有多少对 x, y (1 ≤ x < y ≤ n) 满足

gcd(x, y) = lca(x, y)。

输入格式

每个测试点中包含多组测试数据。输入的第一行包含一个正整数 T (

1 ≤ T ≤ 8 × 105 )，表示数据组数。对于每组测试数据：第一行一个正整数 n (1 ≤ n ≤ 2 × 105 )，表示树的大小。接下来 n − 1 行，每行两个正整数 x, y (1 ≤ x, y ≤ n)，表示树中存在无向边 (x, y)。保证所有测试数据中 n 之和不超过 8 × 105。

输出格式

对于每组测试数据：输出一行一个整数，表示答案。

样例输入

2
5
1 2
2 3
1 4
4 5
10
3 9
4 7
6 9
8 5
5 2
9 1
1 2
2 7
7 10

样例输出

7
27

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第2场）