26618번 - 정기 모임 4

문제

정점이 $N$개인 트리가 주어진다. 각 정점은 1ドル$번부터 $N$번까지 차례대로 번호가 부여되어 있다. $i$번째 간선은 $A_i$번 정점과 $B_i$번 정점을 연결하며, 가중치는 양의 짝수 $C_i$이다. $(1 \le i < N)$

트리에서 정점 사이의 거리는 두 정점 사이에 존재하는 유일한 단순 경로에 포함되는 간선의 가중치의 합으로 정의한다. 또한, 정점과 간선 사이의 거리는 그 정점과 간선의 양끝 정점 사이의 거리들의 평균으로 정의한다. 간선의 가중치가 양의 짝수이므로, 임의의 정점과 간선 사이의 거리는 양의 정수임을 알 수 있다.

트리의 각 정점에 사는 사람들이 $Q$개의 모임을 개최하려 한다. 2년 반에 걸친 사회적 거리두기가 해제됨에 따라, 사람들은 이제 심심한 집에서 나와 오랜만에 보는 간선에서 모일 예정이다. 그러나 추운 겨울에 간선에서 다른 사람을 오래 기다리는 것은 매우 힘들고 귀찮은 일이다. 따라서, 간선과의 거리가 같은 정점들에 사는 사람들끼리만 미리 연락한 후 각자의 정점에서 동시에 출발하여 그 간선에서 동시에 만날 것이다.

$i$번째 모임에는 $E_i$번 간선과의 거리가 $D_i$인 정점에 사는 모든 사람들이 참석한다. $(1 \le i \le Q)$ 이때 모이는 인원을 구해 보자.

입력

첫 번째 줄에 트리의 정점 개수를 의미하는 자연수 $N$과 모임이 개최되는 횟수를 의미하는 자연수 $Q$가 공백을 사이에 두고 주어진다.

두 번째 줄부터 $(N-1)$개의 줄에 걸쳐, 트리의 간선에 관한 정보가 주어진다. $(1+i)$번째 줄에는 세 개의 자연수 $A_i, B_i, C_i$가 공백을 사이에 두고 주어진다. $(1 \leq i < N)$ 이는 $A_i$번 정점과 $B_i$번 정점을 연결하는 가중치 $C_i$의 간선이 존재함을 의미한다.

$(N+1)$번째 줄부터 $Q$개의 줄에 걸쳐, $Q$개의 모임에 관한 정보가 주어진다. $(N+i)$번째 줄에는 $i$번째 모임을 나타내는 두 개의 자연수 $E_i$와 $D_i$가 공백을 사이에 두고 주어진다. $(1 \leq i \leq Q)$

출력

첫 번째 줄부터 $Q$개의 줄에 걸쳐, 답을 차례대로 출력한다. $i$번째 줄에는 $i$번째 모임에 모이는 인원을 출력한다.

제한

• 2ドル \leq N \leq 10^5$
• 1ドル \leq Q \leq 10^5$
• 1ドル \leq A_i, B_i \leq N$ $(1 \leq i < N)$
• 2ドル \leq C_i \leq 10^4, C_i$는 양의 짝수 $(1 \leq i < N)$
• 1ドル \leq E_i < N$ $(1 \leq i \leq Q)$
• 1ドル \leq D_i \leq 10^9$ $(1 \leq i \leq Q)$

힌트