cho.sh정기 모임 4
아직 제출이 없습니다시간 제한4초메모리 제한512 MB문제
정점이 N개인 트리가 주어진다. 각 정점은 1번부터 N번까지 차례대로 번호가 부여되어 있다. i번째 간선은 A_i번 정점과 B_i번 정점을 연결하며, 가중치는 양의 짝수 C_i이다. (1≤i<N)
트리에서 정점 사이의 거리는 두 정점 사이에 존재하는 유일한 단순 경로에 포함되는 간선의 가중치의 합으로 정의한다. 또한, 정점과 간선 사이의 거리는 그 정점과 간선의 양끝 정점 사이의 거리들의 평균으로 정의한다. 간선의 가중치가 양의 짝수이므로, 임의의 정점과 간선 사이의 거리는 양의 정수임을 알 수 있다.
트리의 각 정점에 사는 사람들이 Q개의 모임을 개최하려 한다. 2년 반에 걸친 사회적 거리두기가 해제됨에 따라, 사람들은 이제 심심한 집에서 나와 오랜만에 보는 간선에서 모일 예정이다. 그러나 추운 겨울에 간선에서 다른 사람을 오래 기다리는 것은 매우 힘들고 귀찮은 일이다. 따라서, 간선과의 거리가 같은 정점들에 사는 사람들끼리만 미리 연락한 후 각자의 정점에서 동시에 출발하여 그 간선에서 동시에 만날 것이다.
i번째 모임에는 E_i번 간선과의 거리가 D_i인 정점에 사는 모든 사람들이 참석한다. (1≤i≤Q) 이때 모이는 인원을 구해 보자.
입력
첫 번째 줄에 트리의 정점 개수를 의미하는 자연수 N과 모임이 개최되는 횟수를 의미하는 자연수 Q가 공백을 사이에 두고 주어진다.
두 번째 줄부터 (N−1)개의 줄에 걸쳐, 트리의 간선에 관한 정보가 주어진다. (1+i)번째 줄에는 세 개의 자연수 A_i,B_i,C_i가 공백을 사이에 두고 주어진다. (1≤i<N) 이는 A_i번 정점과 B_i번 정점을 연결하는 가중치 C_i의 간선이 존재함을 의미한다.
(N+1)번째 줄부터 Q개의 줄에 걸쳐, Q개의 모임에 관한 정보가 주어진다. (N+i)번째 줄에는 i번째 모임을 나타내는 두 개의 자연수 E_i와 D_i가 공백을 사이에 두고 주어진다. (1≤i≤Q)
출력
첫 번째 줄부터 Q개의 줄에 걸쳐, 답을 차례대로 출력한다. i번째 줄에는 i번째 모임에 모이는 인원을 출력한다.
제한
- 2≤N≤105
- 1≤Q≤105
- 1≤A_i,B_i≤N (1≤i<N)
- 2≤C_i≤104,C_i는 양의 짝수 (1≤i<N)
- 1≤E_i<N (1≤i≤Q)
- 1≤D_i≤109 (1≤i≤Q)