← 返回题目列表

Codeforces · 1454/E

E. 简单路径的数量

中文机器翻译题面 查看原题

给您一个由 $$$n$$$ 个顶点和 $$$n$$$ 边组成的无向图。保证给定的图是连通的(即可以从任何其他顶点到达任何顶点)并且图中不存在自环和多条边。

您的任务是计算给定图中长度至少为 $$$1$$$ 的简单路径的数量。请注意,仅方向不同的路径被视为相同(即您必须计算无向路径的数量)。例如,路径 $$$[1, 2, 3]$$$ 和 $$$[3, 2, 1]$$$ 被视为相同。

您必须回答 $$$t$$$ 独立测试用例。

回想一下,图中的路径是顶点 $$$v_1, v_2, \ldots, v_k$$$ 的序列,使得该序列中的每对相邻(连续)顶点由一条边连接。路径的长度是其中的边数。简单路径是其中所有顶点都不同的路径。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — 图中的顶点数(和边数)。

测试用例的接下来 $$$n$$$ 行描述边:边 $$$i$$$ 被指定为一对顶点 $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$),其中 $$$u_i$$$ 和$$$v_i$$$ 是第 $$$i$$$ 条边连接的顶点。对于每一对顶点 $$$(u, v)$$$,$$$u$$$ 和 $$$v$$$ 之间至多有一条边。从顶点到自身没有边。因此,图中不存在自环和重边。该图是无向的,i。 e.它的所有边缘都是双向的。该图是连通的,i。 e.通过沿着图的边移动,可以从任何其他顶点到达任何顶点。

保证$$$n$$$之和不超过$$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$)。

输出

对于每个测试用例,打印一个整数:给定图中长度至少为 $$$1$$$ 的简单路径的数量。请注意,仅方向不同的路径被视为相同(即您必须计算无向路径的数量)。

示例

输入 #1

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

输出 #1

6
11
18

注意

考虑示例的第二个测试用例。看起来像这样:

有 $$$11$$$ 不同的简单路径:

1. $$$[1, 2]$$$;
2. $$$[2, 3]$$$;
3. $$$[3, 4]$$$;
4. $$$[2, 4]$$$;
5. $$$[1, 2, 4]$$$;
6. $$$[1, 2, 3]$$$;
7. $$$[2, 3, 4]$$$;
8. $$$[2, 4, 3]$$$;
9. $$$[3, 2, 4]$$$;
10. $$$[1, 2, 3, 4]$$$;
11. $$$[1, 2, 4, 3]$$$.