{"problem":{"name":"C. Kuro and Walking Route","description":{"content":"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","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF979C"},"statements":[{"statement_type":"Markdown","content":"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 \\neq v$) and walk from $u$ using the shortest path to $v$ (note that $(u, v)$ is considered to be different from $(v, u)$).\n\nOddly, 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.\n\nKuro 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.\n\n## Input\n\nThe first line contains three integers $n$, $x$ and $y$ ($1 \\leq n \\leq 3 \\cdot 10^5$, $1 \\leq x, y \\leq n$, $x \\ne y$) - the number of towns, index of the town Flowrisa and index of the town Beetopia, respectively.\n\n$n - 1$ lines follow, each line contains two integers $a$ and $b$ ($1 \\leq a, b \\leq n$, $a \\ne b$), describes a road connecting two towns $a$ and $b$.\n\nIt 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\n## Output\n\nA single integer resembles the number of pair of towns $(u, v)$ that Kuro can use as his walking route.\n\n[samples]\n\n## Note\n\nOn the first example, Kuro can choose these pairs:\n\n*   $(1, 2)$: his route would be $1 \\rightarrow 2$,\n*   $(2, 3)$: his route would be $2 \\rightarrow 3$,\n*   $(3, 2)$: his route would be $3 \\rightarrow 2$,\n*   $(2, 1)$: his route would be $2 \\rightarrow 1$,\n*   $(3, 1)$: his route would be $3 \\rightarrow 2 \\rightarrow 1$.\n\nKuro can't choose pair $(1, 3)$ since his walking route would be $1 \\rightarrow 2 \\rightarrow 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).\n\nOn the second example, Kuro can choose the following pairs:\n\n*   $(1, 2)$: his route would be $1 \\rightarrow 2$,\n*   $(2, 1)$: his route would be $2 \\rightarrow 1$,\n*   $(3, 2)$: his route would be $3 \\rightarrow 1 \\rightarrow 2$,\n*   $(3, 1)$: his route would be $3 \\rightarrow 1$.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Kuro 生活在一个名为 Uberland 的国家，该国有 $n$ 个城镇，编号从 $1$ 到 $n$，以及 $n - 1$ 条双向道路连接这些城镇。任意两个城镇之间都可以互相到达。每条道路连接两个城镇 $a$ 和 $b$。Kuro 热爱散步，他计划参加一场步行马拉松，他将选择一对城镇 $(u, v)$（$u \\ne v$），并从 $u$ 沿最短路径走到 $v$（注意 $(u, v)$ 与 $(v, u)$ 被视为不同的配对）。\n\n奇怪的是，Uberland 中有两个特殊城镇，分别名为 Flowrisa（编号为 $x$）和 Beetopia（编号为 $y$）。Flowrisa 是一个有许多浓香花朵的城镇，而 Beetopia 是一个有许多蜜蜂生活的城镇。具体来说，如果 Kuro 在从 $u$ 到 $v$ 的路径上，先经过 Flowrisa 后再经过 Beetopia，他将避免选择这样的城镇对 $(u, v)$，因为蜜蜂会被 Kuro 身上的花香吸引并蜇他。\n\nKuro 想知道有多少对城镇 $(u, v)$ 可以作为他的步行路线。由于他并不聪明，他请你帮他解决这个问题。\n\n第一行包含三个整数 $n$、$x$ 和 $y$（$1 \\le n \\le 3 \\cdot 10^5$，$1 \\le x, y \\le n$，$x \\ne y$），分别表示城镇数量、Flowrisa 城镇的编号和 Beetopia 城镇的编号。\n\n接下来 $n - 1$ 行，每行包含两个整数 $a$ 和 $b$（$1 \\le a, b \\le n$，$a \\ne b$），描述一条连接城镇 $a$ 和 $b$ 的道路。\n\n保证从每个城镇都可以通过给定的道路到达其他所有城镇。也就是说，给定的城镇和道路地图是一棵树。\n\n输出一个整数，表示 Kuro 可以作为步行路线的城镇对 $(u, v)$ 的数量。\n\n在第一个例子中，Kuro 可以选择以下配对：\n\nKuro 不能选择配对 $(1, 3)$，因为他的步行路线是 $1 \\to 2 \\to 3$，其中他先经过城镇 $1$（Flowrisa），再经过城镇 $3$（Beetopia），这是不允许的（注意配对 $(3, 1)$ 仍然是允许的，因为虽然 Kuro 经过了 Flowrisa 和 Beetopia，但他没有按这个顺序经过它们）。\n\n在第二个例子中，Kuro 可以选择以下配对：\n\n## Input\n\n第一行包含三个整数 $n$、$x$ 和 $y$（$1 \\le n \\le 3 \\cdot 10^5$，$1 \\le x, y \\le n$，$x \\ne y$），分别表示城镇数量、Flowrisa 城镇的编号和 Beetopia 城镇的编号。接下来 $n - 1$ 行，每行包含两个整数 $a$ 和 $b$（$1 \\le a, b \\le n$，$a \\ne b$），描述一条连接城镇 $a$ 和 $b$ 的道路。保证从每个城镇都可以通过给定的道路到达其他所有城镇。也就是说，给定的城镇和道路地图是一棵树。\n\n## Output\n\n输出一个整数，表示 Kuro 可以作为步行路线的城镇对 $(u, v)$ 的数量。\n\n[samples]\n\n## Note\n\n在第一个例子中，Kuro 可以选择以下配对：$(1, 2)$：他的路线是 $1 \\to 2$；$(2, 3)$：他的路线是 $2 \\to 3$；$(3, 2)$：他的路线是 $3 \\to 2$；$(2, 1)$：他的路线是 $2 \\to 1$；$(3, 1)$：他的路线是 $3 \\to 2 \\to 1$。Kuro 不能选择配对 $(1, 3)$，因为他的步行路线是 $1 \\to 2 \\to 3$，其中他先经过城镇 $1$（Flowrisa），再经过城镇 $3$（Beetopia），这是不允许的（注意配对 $(3, 1)$ 仍然是允许的，因为虽然 Kuro 经过了 Flowrisa 和 Beetopia，但他没有按这个顺序经过它们）。\n\n在第二个例子中，Kuro 可以选择以下配对：$(1, 2)$：他的路线是 $1 \\to 2$；$(2, 1)$：他的路线是 $2 \\to 1$；$(3, 2)$：他的路线是 $3 \\to 1 \\to 2$；$(3, 1)$：他的路线是 $3 \\to 1$。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T = (V, E) $ be a tree with $ n $ vertices (towns), labeled $ 1 $ to $ n $.  \nLet $ x, y \\in V $, $ x \\ne y $, denote the special towns Flowrisa and Beetopia, respectively.  \n\nLet $ P(u, v) $ denote the unique simple path from vertex $ u $ to vertex $ v $ in $ T $.  \nLet $ \\text{order}(P(u, v)) $ denote the sequence of vertices along $ P(u, v) $, starting at $ u $ and ending at $ v $.  \n\n**Constraints**  \n1. $ 1 \\le n \\le 3 \\cdot 10^5 $  \n2. $ 1 \\le x, y \\le n $, $ x \\ne y $  \n3. The graph is a tree: connected and acyclic.  \n\n**Forbidden Condition**  \nA pair $ (u, v) $, $ u \\ne v $, is **forbidden** if and only if in $ \\text{order}(P(u, v)) $, vertex $ x $ appears **before** vertex $ y $.  \n\n**Objective**  \nCompute the number of ordered pairs $ (u, v) $, $ u \\ne v $, such that $ (u, v) $ is **not forbidden**, i.e., either:  \n- $ x $ does not appear on $ P(u, v) $, or  \n- $ y $ appears on $ P(u, v) $ before $ x $, or  \n- neither $ x $ nor $ y $ is on $ P(u, v) $.  \n\nEquivalently, count:  \n$$\n\\left| \\left\\{ (u, v) \\in V \\times V \\mid u \\ne v \\text{ and } \\text{if } x, y \\in P(u, v) \\text{ then } y \\text{ precedes } x \\text{ in } \\text{order}(P(u, v)) \\right\\} \\right|\n$$\n\n**Note**: Total possible pairs: $ n(n - 1) $.  \nLet $ F $ be the set of forbidden pairs: $ F = \\{ (u, v) \\mid x \\text{ appears before } y \\text{ on } P(u, v) \\} $.  \nThen the answer is:  \n$$\nn(n - 1) - |F|\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF979C","tags":["dfs and similar","trees"],"sample_group":[["3 1 3\n1 2\n2 3","5"],["3 1 3\n1 2\n1 3","4"]],"created_at":"2026-03-03 11:00:39"}}