← 返回题目列表

Codeforces · 979/C

C. 黑与步行路线

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

Kuro 生活在一个叫做 Uberland 的国家,由 $$$n$$$ 个城镇组成,编号从 $$$1$$$ 到 $$$n$$$,以及连接这些城镇的 $$$n - 1$$$ 双向道路。从任何其他城镇都可以到达每个城镇。每条道路连接两个城镇 $$$a$$$ 和 $$$b$$$。 Kuro喜欢步行,他计划参加步行马拉松,其中他将选择一对城镇$$$(u, v)$$$ ($$$u \neq v$$$),并从$$$u$$$使用最短路径步行到$$$v$$$(注意$$$(u, v)$$$被认为与$$$(v, u)$$$不同)。

奇怪的是,Uberland 有 2 个特殊城镇,分别为 Flowrisa(用索引 $$$x$$$ 表示)和 Beetopia(用索引 $$$y$$$ 表示)。弗洛里萨(Flowrisa)是一个有许多浓烈花朵的小镇,而贝托皮亚(Beetopia)是另一个有许多蜜蜂居住的小镇。特别是,如果在从$$$u$$$到$$$v$$$的路径上,Kuro在到达Flowrisa后到达Beetopia,那么Kuro将避开任何一对城镇$$$(u, v)$$$,因为蜜蜂会被Kuro身上的花香吸引并蜇他。

Kuro 想知道他可以选择多少对城市 $$$(u, v)$$$ 作为他的路线。由于他不太聪明,所以他请你帮助他解决这个问题。

输入

第一行包含三个整数 $$$n$$$、$$$x$$$ 和 $$$y$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$, $$$1 \leq x, y \leq n$$$, $$$x \ne y$$$) - 城镇数量、城镇 Flowrisa 的索引和城镇的索引分别是 Beetopia。

$$$n - 1$$$ 行,每行包含两个整数 $$$a$$$ 和 $$$b$$$ ($$$1 \leq a, b \leq n$$$, $$$a \ne b$$$),描述一条连接两个城镇 $$$a$$$ 和 $$$b$$$ 的道路。

保证从每个城镇,我们都可以使用给定的道路到达城市中的每个其他城镇。也就是说,给定的城镇和道路地图是一棵树。

输出

一个整数类似于 Kuro 可以用作步行路线的城镇对 $$$(u, v)$$$ 的数量。

示例

输入 #1

3 1 3
1 2
2 3

输出 #1

5

输入 #2

3 1 3
1 2
1 3

输出 #2

4

注意

在第一个示例中,Kuro 可以选择以下对:

- $$$(1, 2)$$$:他的路线是 $$$1 \rightarrow 2$$$,
- $$$(2, 3)$$$:他的路线是 $$$2 \rightarrow 3$$$,
- $$$(3, 2)$$$:他的路线是 $$$3 \rightarrow 2$$$,
- $$$(2, 1)$$$:他的路线是 $$$2 \rightarrow 1$$$,
- $$$(3, 1)$$$:他的路线是 $$$3 \rightarrow 2 \rightarrow 1$$$。

Kuro 无法选择 $$$(1, 3)$$$ 配对,因为他的步行路线为 $$$1 \rightarrow 2 \rightarrow 3$$$,其中 Kuro 访问城镇 $$$1$$$ (Flowrisa),然后访问城镇 $$$3$$$ (Beetopia),这是不允许的(请注意,$$$(3, 1)$$$ 配对仍然是允许的,因为尽管 Kuro 访问过Flowrisa 和 Beetopia,他没有按这个顺序访问它们)。

在第二个示例中,Kuro 可以选择以下对:

- $$$(1, 2)$$$:他的路线是 $$$1 \rightarrow 2$$$,
- $$$(2, 1)$$$:他的路线是 $$$2 \rightarrow 1$$$,
- $$$(3, 2)$$$:他的路线是 $$$3 \rightarrow 1 \rightarrow 2$$$,
- $$$(3, 1)$$$:他的路线是 $$$3 \rightarrow 1$$$。