시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 34 | 14 | 13 | 39.394% |
심부름을 잘하는 곰곰이는 최근 배달 아르바이트를 할 기회를 얻었다.
곰곰이의 나라에는 특이하게도 배달 주문을 들어온 순서대로 2개씩 묶어 처리해야 한다는 법이 있어서, 곰곰이도 한 번 출발하면 2개의 도시를 순서대로 들러야 한다. 배달 주문 하나는 따라서 도시 3개의 튜플 $(A, B, C)$로 표현이 가능하고, 이는 곰곰이가 음식점이 있는 $A$도시에서 출발하여 $B$도시까지 최단경로로 이동, 다시 $B$도시에서 $C$도시까지 최단경로로 이동한다는 것을 의미한다. 곰곰이의 나라는 트리 형태이고, 따라서 $N$개의 도시가 $N-1$개의 양방향 도로로 이어져 있으며 연결그래프를 이룬다.
치킨을 좋아하는 곰곰이는 이번에도 역시 기회가 될 때마다 닭 다리를 사려고 한다. 곰곰이는 이동하는 중간에 들르는 도시에서 닭 다리를 구매할 수 있으며, 각 도시에서는 최대 한 개의 닭 다리를 구매할 수 있다. 배달 주문을 완료하는 시점에는 닭 다리가 정확히 두 개 있어야 한다.
곰곰이는 배달 주문을 처리할 때마다, 노트에 자신이 닭 다리를 산 도시의 순서쌍을 적어둔다. 예를 들어 $3$번 도시에서 닭 다리를 산 뒤, $1$번 도시에서 닭 다리를 샀으면 $(3, 1)$로 표기한다.
각 주문별로 만들어질 수 있는 순서쌍의 개수를 구해보자.
첫째 줄에 도시의 개수 $N$, 배달 주문의 개수 $Q\ (1 \leq N, Q \leq 100\,000)$가 공백을 사이에 두고 주어진다.
둘째 줄부터 $N-1$줄에 걸쳐 정수 $u$, $v$ 가 공백을 사이에 두고 주어진다. 이는 $u$ 도시와 $v$ 도시를 잇는 양방향 도로가 있음을 의미한다. $(1 \leq u, v \leq N)$
$N+1$째 줄부터 $Q$개의 줄에 걸쳐 배달 주문 $(A, B, C)$의 정수 $A, B, C$ $(1 \le A, B, C \le N)$ 가 공백을 사이에 두고 주어진다.
$Q$개의 줄에 걸쳐, 각 배달 주문별로 만들어질 수 있는 순서쌍의 개수를 출력한다.
5 3 1 2 2 3 3 4 3 5 1 5 4 1 1 1 2 3 4
11 0 3
8 5 1 2 2 3 3 4 3 5 6 4 5 7 7 8 6 1 2 4 3 1 7 8 8 3 1 8 5 4 2
11 6 1 18 7