CF979C.Kuro and Walking Route
普及/提高-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Kuro is living in a country called Uberland, consisting of n towns, numbered from 1 to n, and n−1 bidirectional roads connecting these towns. It is possible to reach each town from any other. Each road connects two towns a and b. Kuro loves walking and he is planning to take a walking marathon, in which he will choose a pair of towns (u,v) (u=v) and walk from u using the shortest path to v (note that (u,v) is considered to be different from (v,u)).
Oddly, there are 2 special towns in Uberland named Flowrisa (denoted with the index x) and Beetopia (denoted with the index y). Flowrisa is a town where there are many strong-scent flowers, and Beetopia is another town where many bees live. In particular, Kuro will avoid any pair of towns (u,v) if on the path from u to v, he reaches Beetopia after he reached Flowrisa, since the bees will be attracted with the flower smell on Kuro’s body and sting him.
Kuro wants to know how many pair of city (u,v) he can take as his route. Since he’s not really bright, he asked you to help him with this problem.
Kuro 生活在一个名为“优伯兰”(Uberland)的国家,该国由 n 座城镇组成,编号从 1 到 n,以及 n−1 条双向道路连接这些城镇。任意两座城镇之间均可通过道路相互到达。每条道路连接两座城镇 a 和 b。Kuro 热爱步行,他正计划举办一场“步行马拉松”,在其中他将选择一对城镇 (u,v)(满足 u=v),并从 u 出发,沿最短路径步行至 v(注意:(u,v) 被视为与 (v,u) 不同)。
奇怪的是,优伯兰中有两座特殊城镇,分别名为“弗洛瑞莎”(Flowrisa,编号为 x)和“蜜蜂坡”(Beetopia,编号为 y)。弗洛瑞莎盛产气味浓烈的花朵,而蜜蜂坡则栖息着大量蜜蜂。特别地,若 Kuro 在从 u 到 v 的路径上先经过弗洛瑞莎、再经过蜜蜂坡,他便会避开该对城镇 (u,v)——因为沾染在 Kuro 身上的花香会吸引蜜蜂,进而叮咬他。
Kuro 想知道他总共可以选择多少对城镇 (u,v) 作为他的步行路线。由于他并不十分聪明,他请你帮忙解决这个问题。
输入格式
The first line contains three integers n, x and y (1≤n≤3⋅105, 1≤x,y≤n, x=y) - the number of towns, index of the town Flowrisa and index of the town Beetopia, respectively.
n−1 lines follow, each line contains two integers a and b (1≤a,b≤n, a=b), describes a road connecting two towns a and b.
It is guaranteed that from each town, we can reach every other town in the city using the given roads. That is, the given map of towns and roads is a tree.
第一行包含三个整数 n、x 和 y(1≤n≤3⋅105,1≤x,y≤n,x=y),分别表示城镇的数量、Flowrisa 城镇的编号以及 Beetopia 城镇的编号。
接下来 n−1 行,每行包含两个整数 a 和 b(1≤a,b≤n,a=b),表示一条连接城镇 a 和城镇 b 的道路。
保证从任意一个城镇出发,均可通过给定的道路到达城市中的任意其他城镇。即,给定的城镇与道路构成一棵树。
输出格式
A single integer resembles the number of pair of towns (u,v) that Kuro can use as his walking route.
一个整数,表示黑郎可以作为其步行路线的城镇对 (u,v) 的数量。
输入输出样例
输入#1
3 1 3 1 2 2 3
输出#1
5
输入#2
3 1 3 1 2 1 3
输出#2
4
说明/提示
On the first example, Kuro can choose these pairs:
- (1,2): his route would be 1→2,
- (2,3): his route would be 2→3,
- (3,2): his route would be 3→2,
- (2,1): his route would be 2→1,
- (3,1): his route would be 3→2→1.
Kuro can't choose pair (1,3) since his walking route would be 1→2→3, in which Kuro visits town 1 (Flowrisa) and then visits town 3 (Beetopia), which is not allowed (note that pair (3,1) is still allowed because although Kuro visited Flowrisa and Beetopia, he did not visit them in that order).
On the second example, Kuro can choose the following pairs:
- (1,2): his route would be 1→2,
- (2,1): his route would be 2→1,
- (3,2): his route would be 3→1→2,
- (3,1): his route would be 3→1.
在第一个样例中,Kuro 可以选择以下数对:
- (1,2):他的路径为 1→2,
- (2,3):他的路径为 2→3,
- (3,2):他的路径为 3→2,
- (2,1):他的路径为 2→1,
- (3,1):他的路径为 3→2→1。
Kuro 不能选择数对 (1,3),因为他的行走路径将是 1→2→3,其中 Kuro 先访问了城镇 1(Flowrisa),再访问了城镇 3(Beetopia),这是不允许的(注意:数对 (3,1) 仍是允许的,因为尽管 Kuro 访问了 Flowrisa 和 Beetopia,但他并未按此顺序访问它们)。
在第二个样例中,Kuro 可以选择以下数对:
- (1,2):他的路径为 1→2,
- (2,1):他的路径为 2→1,
- (3,2):他的路径为 3→1→2,
- (3,1):他的路径为 3→1。
输入解题思路,AI测评打分。不知道怎么写?