Informatica Online Judge

  토끼 사냥 #1 [2349 / 092D]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 16   Total Tried : 28


The Champion of this Problem (C++) : gs17078 - ms / 790byte
My Best Submission (C++) : N/A

[36th 안지민 (gs18070)]
Writer ID : [gs18070]

Background

레트로는 달에 사는 옥토끼를 잡으려 달에 탐사를 떠나려 한다. 옥토끼들은 달의 표면에 있는 크레이터에 나타난다.
연구 결과, 달의 크레이터들은 N개의 정점과 N-1개의 간선을 갖고, 1번 크레이터를 루트로 갖는 트리 구조를 이루고 있다.
또, 현재 각 트레이터에는 토끼가 0마리 존재하지만, di번째 날 이후부터는 i번째 크레이터에 ci마리의 토끼가 존재한다.
레트로가 i번 정점으로 탐사를 떠날 경우 i번째 크레이터를 루트로 하는 서브 트리의 각 크레이터에 존재하는 모든 토끼를 잡을 수 있다.
레트로는 달 탐사를 떠나기 전 Q번의 시뮬레이션을 진행하기로 했다.
j번째 시뮬레이션에서는 nj번째 크레이터로 탐사를 떠나서 최소 sj만큼의 토끼를 잡으려고 계획한다.
이때, sj 이상 만큼 토끼를 잡을때 까지 걸리는 시간(날짜 수)의 최솟값을 구해줘야 한다.
레트로에게 시뮬레이션 결과를 구해주는 프로그램을 작성해 주자!!

Input

첫번째 줄에 크레이터 수를 나타내는 N과 시뮬레이션 횟수를 나타내는 Q가 공백을 두고 주어진다. (1 <= N <= 1000, 1 <= Q <= 1000)
그 다음 N개의 줄에 pi, di, ci가 공백을 두고 주어진다. pi는 i번째 크레이터의 부모 크레이터 번호(i가 1일 경우 0), di와 ci는 각각 토끼가 생기는 날, 생기는 토끼의 숫자를 나타낸다. (0 <= pi < i, 1 <= di <= 100000, 0 <= ci <= 100000)
그 다음 Q개의 줄에 nj와 sj가 공백을 두고 주어진다. nj는 탐사를 떠나는 크레이터 번호, sj는 목표 토끼 숫자다. (1 <= nj <= N, 1 <= sj <= 100000)

Output

Q개의 줄에 각 시뮬레이션시 걸리는 최소 날짜 수를 출력한다. 만약, 아무리 오래 기다려도 목표 토끼 숫자 이상의 토끼를 잡을 수 없을 경우 -1을 출력한다.

IO Example

입력
5 3
0 1 2
1 3 4
1 4 10
2 2 7
2 5 2
1 10
2 8
3 9

출력
3
3
4

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]