32258번 - 트리와 경로 뒤집기 쿼리

$N$개의 정점과 $(N-1)$개의 간선을 가진 그래프가 주어진다. 정점은 $1$번부터 $N$번까지 번호가 매겨져 있다. 각 간선은 방향성이 있으며, 모든 간선의 방향성을 제거할 경우 이 그래프는 트리가 된다.

아래의 쿼리를 수행하는 프로그램을 작성하시오.

• $u$ $v$: 모든 간선의 방향성을 제거했을 때 $u$번 정점과 $v$번 정점을 잇는 단순 경로에 있는 간선의 방향성을 모두 뒤집는다. 이후 간선의 방향성을 고려했을 때 $a$번 정점에서 $b$번 정점으로 도달할 수 있는 순서쌍 $(a,b)$의 개수를 출력한다.

첫째 줄에 양의 정수 $N$이 주어진다. ($2\le N\le 100\, 000$)

둘째 줄부터 $(N-1)$개의 줄에 그래프의 정보가 주어진다. 각 줄에 양의 정수 $x$와 $y$가 공백을 사이에 두고 주어진다. ($1\le x,y\le N$; $x\neq y$) 이는 $x$에서 $y$로 향하는 간선이 존재함을 뜻한다.

다음 줄에 쿼리의 개수 $Q$가 주어진다. ($1\le Q\le 100\, 000$)

다음 $Q$개의 줄에 쿼리가 한 줄에 하나씩 주어진다. 각 줄에는 쿼리를 나타내는 두 정수 $u$와 $v$가 공백을 사이에 두고 주어진다. ($1\le u,v\le N$; $u\neq v$)

$Q$개의 줄에 걸쳐, 각 쿼리의 결과를 순서대로 한 줄에 하나씩 출력한다.