정기 모임 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 \le i < N)$ 이는 $A_i$번 정점과 $B_i$번 정점을 가중치 $C_i$인 간선으로 잇는다는 뜻이다.

$(N+1)$번째 줄부터 $Q$개의 줄에 모임 정보가 주어진다. $(N+i)$번째 줄에는 자연수 $E_i$와 $D_i$가 공백으로 구분되어 주어진다. $(1 \le i \le Q)$

$Q$개의 줄에 걸쳐, $i$번째 줄에 $i$번째 모임에 모이는 인원을 출력한다.

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