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)$).

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.


-----Input-----

The 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 - 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$.

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.


-----Output-----

A single integer resembles the number of pair of towns $(u, v)$ that Kuro can use as his walking route.


-----Examples-----
Input
3 1 3
1 2
2 3

Output
5
Input
3 1 3
1 2
1 3

Output
4


-----Note-----

On the first example, Kuro can choose these pairs:   $(1, 2)$: his route would be $1 \rightarrow 2$,  $(2, 3)$: his route would be $2 \rightarrow 3$,  $(3, 2)$: his route would be $3 \rightarrow 2$,  $(2, 1)$: his route would be $2 \rightarrow 1$,  $(3, 1)$: his route would be $3 \rightarrow 2 \rightarrow 1$. 

Kuro 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).

On the second example, Kuro can choose the following pairs:   $(1, 2)$: his route would be $1 \rightarrow 2$,  $(2, 1)$: his route would be $2 \rightarrow 1$,  $(3, 2)$: his route would be $3 \rightarrow 1 \rightarrow 2$,  $(3, 1)$: his route would be $3 \rightarrow 1$.

Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Graph traversal

Starter code:

Solutions:
import sys
input = sys.stdin.readline
from collections import deque
(n, x, y) = list(map(int, input().split()))
x -= 1
y -= 1
graph = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = list(map(int, input().split()))
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
parent = [-1] * n
q = deque([x])
while q:
	node = q.popleft()
	if node == y:
		break
	for i in graph[node]:
		if i == parent[node]:
			continue
		parent[i] = node
		q.append(i)
node = y
y_ = parent[y]
while parent[node] != x:
	node = parent[node]
parent = [-1] * n
parent[x] = node
parent[y] = y_
(a, b) = (0, 0)
q = deque([x])
while q:
	node = q.popleft()
	a += 1
	for i in graph[node]:
		if i == parent[node]:
			continue
		parent[i] = node
		q.append(i)
q = deque([y])
while q:
	node = q.popleft()
	b += 1
	for i in graph[node]:
		if i == parent[node]:
			continue
		parent[i] = node
		q.append(i)
ans = n * (n - 1) - a * b
print(ans)


from collections import defaultdict
(n, x, y) = list(map(int, input().split()))
edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
chk = [False] * (n + 1)
cnt = [1] * (n + 1)
adj = defaultdict(list)
for (u, v) in edges:
	adj[u].append(v)
	adj[v].append(u)

def dfs(y, x, adj):
	vis = set()
	stk = [y]
	stack_order = []
	while stk:
		u = stk.pop()
		vis.add(u)
		if u == x:
			chk[u] = True
		order = []
		for v in adj[u]:
			if v not in vis:
				stk.append(v)
				order.append(v)
		if order:
			stack_order.append((u, order))
	while stack_order:
		u = stack_order.pop()
		for v in u[1]:
			cnt[u[0]] += cnt[v]
			chk[u[0]] |= chk[v]
dfs(y, x, adj)
res = 0
for i in adj[y]:
	if chk[i]:
		res = cnt[y] - cnt[i]
		break
print(n * (n - 1) - res * cnt[x])


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
threading.stack_size(10 ** 8)
sys.setrecursionlimit(300000)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, x, y) = list(map(int, input().split()))
edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
chk = [False] * (n + 1)
cnt = [1] * (n + 1)
adj = defaultdict(list)
for (u, v) in edges:
	adj[u].append(v)
	adj[v].append(u)

def dfs(y, x, adj):
	vis = set()
	stk = [y]
	stack_order = []
	while stk:
		u = stk.pop()
		vis.add(u)
		if u == x:
			chk[u] = True
		order = []
		for v in adj[u]:
			if v not in vis:
				stk.append(v)
				order.append(v)
		if order:
			stack_order.append((u, order))
	while stack_order:
		u = stack_order.pop()
		for v in u[1]:
			cnt[u[0]] += cnt[v]
			chk[u[0]] |= chk[v]
dfs(y, x, adj)
res = 0
for i in adj[y]:
	if chk[i]:
		res = cnt[y] - cnt[i]
		break
print(n * (n - 1) - res * cnt[x])


from collections import defaultdict
(n, flower, bee) = list(map(int, input().split()))
roads = {}
for _ in range(n - 1):
	(x, y) = list(map(int, input().split()))
	if x not in roads:
		roads[x] = [y]
	else:
		roads[x].append(y)
	if y not in roads:
		roads[y] = [x]
	else:
		roads[y].append(x)
flowers = defaultdict(int)

def dfs(bee, flower):
	q = []
	visited = set()
	visited.add(flower)
	last = -1
	for y in roads[flower]:
		if y == bee:
			last = y
			continue
		q.append([y, y])
	while q:
		now = q.pop()
		visited.add(now[0])
		flowers[now[1]] += 1
		for y in roads[now[0]]:
			if y not in visited:
				if y == bee:
					last = now[1]
					continue
				q.append([y, now[1]])
	return last
rem = dfs(bee, flower)
flower_total = sum(flowers.values()) + 1
print(n * (n - 1) - (flower_total - flowers[rem]) * (n - flower_total))


from itertools import combinations, permutations
from collections import defaultdict
import math
import sys
import os
graph = defaultdict(list)

def solution(n, flo, bee):
	cleverBrute = [0] * (n + 1)
	visited = [0] * (n + 1)
	q = []
	cutNode = 0
	for elem in graph[flo]:
		if elem != bee:
			q.append([elem, elem])
		else:
			cutNode = elem
	visited[flo] = 1
	while q:
		temp = q.pop()
		(currentFrom, currentTo) = (temp[0], temp[1])
		visited[currentFrom] = 1
		cleverBrute[currentTo] += 1
		for elem in graph[currentFrom]:
			if not visited[elem]:
				if elem != bee:
					q.append([elem, currentTo])
				else:
					cutNode = currentTo
	return (sum(cleverBrute) + 1 - cleverBrute[cutNode]) * (n - (sum(cleverBrute) + 1))

def main():
	(n, x, y) = map(int, input().strip().split())
	for _ in range(n - 1):
		(u, v) = map(int, input().strip().split())
		graph[u].append(v)
		graph[v].append(u)
	print(n * (n - 1) - solution(n, x, y))

def __starting_point():
	main()
__starting_point()


import sys
import threading
from collections import defaultdict
(n, x, y) = list(map(int, input().split()))
adj = defaultdict(list)
for _ in range(n - 1):
	(a, b) = list(map(int, input().split()))
	adj[a].append(b)
	adj[b].append(a)

def fun(node, par, dest, ans):
	cnt = 1
	for ch in adj[node]:
		if ch != par:
			cnt += fun(ch, node, dest, ans)
	if node == dest:
		ans[0] = cnt * ans[0]
	return cnt

def main():
	ans = [1]
	t = fun(x, 0, y, ans)
	fun(y, 0, x, ans)
	print(t * (t - 1) - ans[0])

def __starting_point():
	sys.setrecursionlimit(10 ** 6)
	threading.stack_size(10 ** 8)
	t = threading.Thread(target=main)
	t.start()
	t.join()
__starting_point()


from collections import defaultdict
(n, x, y) = list(map(int, input().split()))
graph = defaultdict(list)
vis = [False for i in range(n + 1)]
mat = [False for i in range(n + 1)]
subtree = [0 for i in range(n + 1)]
for i in range(n - 1):
	(u, v) = list(map(int, input().split()))
	graph[u].append(v)
	graph[v].append(u)
q = []
cur = 0
for v in graph[x]:
	if v != y:
		q.append([v, v])
	else:
		cur = v
vis[x] = 1
while q != []:
	temp = q.pop()
	(u, v) = temp
	vis[u] = True
	subtree[v] += 1
	for node in graph[u]:
		if vis[node] == False:
			if node != y:
				q.append([node, v])
			else:
				cur = v
val = sum(subtree)
val1 = val + 1 - subtree[cur]
val2 = n - (sum(subtree) + 1)
val = val1 * val2
print(n * (n - 1) - val)


import sys
input = sys.stdin.readline
(n, x, y) = map(int, input().split())
x -= 1
y -= 1
g = [[] for i in range(n)]
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	g[u - 1].append(v - 1)
	g[v - 1].append(u - 1)
q = [x]
par = [-1] * n
vis = [False] * n
vis[x] = True
while q:
	ver = q.pop()
	for to in g[ver]:
		if not vis[to]:
			par[to] = ver
			q.append(to)
			vis[to] = True
yy = par[y]
tmp = y
while par[tmp] != x:
	tmp = par[tmp]
xx = tmp
g[x].remove(xx)
g[xx].remove(x)
if yy in g[y]:
	g[y].remove(yy)
if y in g[yy]:
	g[yy].remove(y)
size_x = 1
size_y = 1
q = [x]
vis = [False] * n
vis[x] = True
while q:
	ver = q.pop()
	for to in g[ver]:
		if not vis[to]:
			size_x += 1
			q.append(to)
			vis[to] = True
q = [y]
vis = [False] * n
vis[y] = True
while q:
	ver = q.pop()
	for to in g[ver]:
		if not vis[to]:
			size_y += 1
			q.append(to)
			vis[to] = True
print(n * (n - 1) - size_x * size_y)


import sys
import threading
from collections import defaultdict
(n, x, y) = map(int, input().split())
adj = defaultdict(list)
for i in range(1, n):
	(a, b) = map(int, input().split())
	adj[a].append(b)
	adj[b].append(a)

def dfs(node, par, v, ans):
	sum = 1
	for i in range(len(adj[node])):
		if adj[node][i] != par:
			sum += dfs(adj[node][i], node, v, ans)
	if node == v:
		ans[0] = sum
	return sum

def main():
	ans1 = [0]
	dfs(x, 0, y, ans1)
	ans2 = [0]
	dfs(y, 0, x, ans2)
	print(n * (n - 1) - ans1[0] * ans2[0])
sys.setrecursionlimit(10 ** 6)
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


def calculate_max_paths(edges, node, dest, par, cnt):
	ans = 1
	for child in edges.get(node, []):
		if child != par:
			ans += calculate_max_paths(edges, child, dest, node, cnt)
	if dest == node:
		cnt[0] = ans
	return ans

def main():
	from collections import defaultdict
	(n, flower, bee) = list(map(int, input().split()))
	edges = defaultdict(list)
	for _ in range(n - 1):
		(x, y) = list(map(int, input().split()))
		edges[x].append(y)
		edges[y].append(x)
	(bees, flowers) = ([0], [0])
	x = calculate_max_paths(edges, flower, bee, par=None, cnt=bees)
	y = calculate_max_paths(edges, bee, flower, par=None, cnt=flowers)
	print(x * (x - 1) - bees[0] * flowers[0])
import sys
import threading
sys.setrecursionlimit(10 ** 6)
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


from __future__ import print_function
from collections import *
from sys import stdin
from bisect import *
from heapq import *
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
rr = lambda x: reversed(range(x))
mod = int(1000000000.0) + 7
inf = float('inf')
(n, x, y) = gil()
adj = [[] for _ in range(n + 1)]
for _ in range(1, n):
	(n1, n2) = gil()
	adj[n1].append(n2)
	adj[n2].append(n1)
st = [x]
dp = [0] * (n + 1)
vis = [0] * (n + 1)
while st:
	p = st[-1]
	if vis[p]:
		st.pop()
		dp[p] = 1
		for c in adj[p]:
			dp[p] += dp[c]
	else:
		vis[p] = 1
		for c in adj[p]:
			if not vis[c]:
				st.append(c)
left = dp[y]
st = [y]
dp = [0] * (n + 1)
vis = [0] * (n + 1)
while st:
	p = st[-1]
	if vis[p]:
		st.pop()
		dp[p] = 1
		for c in adj[p]:
			dp[p] += dp[c]
	else:
		vis[p] = 1
		for c in adj[p]:
			if not vis[c]:
				st.append(c)
ans = n * (n - 1)
ans -= left * dp[x]
print(ans)


import sys
from collections import deque

def get_roots_direct_children(q, roots_direct_children, visited, edges):
	while q:
		root = q.popleft()
		visited[root] = True
		root_direct_children = list()
		for vertice in edges[root]:
			if not visited[vertice]:
				q.appendleft(vertice)
				visited[vertice] = True
				root_direct_children.append(vertice)
		roots_direct_children.append((root, root_direct_children))

def get_cnt(cnt, roots_direct_children):
	while roots_direct_children:
		cur_tuple = roots_direct_children.pop()
		root = cur_tuple[0]
		direct_children = cur_tuple[1]
		for direct_child in direct_children:
			cnt[root] += cnt[direct_child]

def solve():
	input = sys.stdin.readline
	(n, x, y) = map(int, input().split())
	edges = {vertice: list() for vertice in range(1, n + 1)}
	for i in range(n - 1):
		uv = input().split()
		u = int(uv[0])
		v = int(uv[1])
		edges[u].append(v)
		edges[v].append(u)
	cnt = [1 for _ in range(n + 1)]
	visited = [False for _ in range(n + 1)]
	q = deque()
	q.append(x)
	roots_direct_children = list()
	get_roots_direct_children(q, roots_direct_children, visited, edges)
	get_cnt(cnt, roots_direct_children)
	cnt_y = cnt[y]
	q = deque()
	q.append(y)
	roots_direct_children = list()
	cnt = [1 for _ in range(n + 1)]
	visited = [False for _ in range(n + 1)]
	get_roots_direct_children(q, roots_direct_children, visited, edges)
	get_cnt(cnt, roots_direct_children)
	cnt_x = cnt[x]
	total = n * (n - 1)
	not_ok_routes = cnt_x * cnt_y
	result = total - not_ok_routes
	print(result)
solve()


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input().decode().rstrip('\n\r')
from collections import deque as dq
inf = float('inf')
mod = 10 ** 9 + 7

def DFS(gr, B, F):
	n = len(gr)
	vis = [False for i in range(n)]
	fin = [False for i in range(n)]
	dp = [None for i in range(n)]
	par = [-1 for i in range(n)]

	def dfs(node):
		stack = [node]
		while stack:
			node = stack[-1]
			if not vis[node]:
				vis[node] = True
				for i in gr[node]:
					if not vis[i]:
						par[i] = node
						stack.append(i)
			else:
				stack.pop()
				dp[node] = 1
				for i in gr[node]:
					if fin[i]:
						dp[node] += dp[i]
				fin[node] = True
	dfs(B)
	ret = dp[F]
	while par[F] != B:
		F = par[F]
	ret *= dp[B] - dp[F]
	return ret
Cases = 1
for Case in range(Cases):
	(n, x, y) = rl()
	gr = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v) = rl()
		u -= 1
		v -= 1
		gr[v].append(u)
		gr[u].append(v)
	FtoB = DFS(gr, y - 1, x - 1)
	ans = n * (n - 1) - FtoB
	print(max(0, ans))


from collections import defaultdict
(n, x, y) = list(map(int, input().split()))
sub_checks = [False] * (n + 1)
sub_count = [1] * (n + 1)

def dfs(y, x, graph):
	visited = set()
	s = [y]
	stack_order = []
	while len(s) != 0:
		curr = s.pop()
		visited.add(curr)
		if curr == x:
			sub_checks[curr] = True
		order = []
		for child in graph[curr]:
			if child not in visited:
				s.append(child)
				order.append(child)
		if len(order) != 0:
			stack_order.append((curr, order))
	while len(stack_order) != 0:
		curr = stack_order.pop()
		for child in curr[1]:
			sub_count[curr[0]] += sub_count[child]
			sub_checks[curr[0]] |= sub_checks[child]
graph = defaultdict(list)
for _ in range(n - 1):
	edge = list(map(int, input().split()))
	graph[edge[0]].append(edge[1])
	graph[edge[1]].append(edge[0])
dfs(y, x, graph)
exclude = 0
for child in graph[y]:
	if sub_checks[child]:
		exclude = sub_count[y] - sub_count[child]
		break
print(n * (n - 1) - exclude * sub_count[x])