IOI 2009- 강줄기 > 문제은행 : 정보올림피아드&알고리즘




2545 : 강줄기

제한시간
8000 ms   
메모리제한
256 MB   
해결횟수
5 회   
시도횟수
77 회   

문제

훌륭한 자연경관을 가지고 있어서 관광객이 많이 오는 A산에 강이 흐르는데, 강줄기에 N개의 시설이 있다. (강줄기가 갈라져 있을 수 있다.)

이 시설들을 편의상 1번~N번으로 번호를 붙이자. 

각각의 시설들은 총 F가지(식당, 생태체험관 등등)의 특징으로 분류된다.

 

A산의 관광 컨텐츠를 개발하는 담당을 맡은 지헌이는 강줄기를 따라 래프팅을 하면서 이동하는 방식의 새로운 이동수단을 개발했다. 

지헌이의 아이디어가 A산에 적용되었다.

하지만 강물은 위에서 아래로만 흐르기 때문에 한 시설에서 래프팅 보트를 타면 무조건 특정한 다른 시설로 가게 된다. 

단, 1번 시설은 강의 최하류에 위치해 있기 때문에 1번 시설에서는 어디로도 더 이상 갈 수 없고, 또한 어떤 시설에서도 1번 시설로 갈 수 있다.

 

요즘 들어서 여행 계획을 짜는 사람들이 많아지고 있는데, M명의 사람들은 각각 특징이 Si인 시설에서 특징이 Ei인 시설로 가고 싶어한다. 

A산의 강줄기가 상당히 복잡하기 때문에, 지헌이는 특징이 Si인 시설에서 특징이 Ei인 시설로 갈 수 있는 방법의 수를 계산하는 것에 무리가 생겼고, 

프로그래머인 당신에게 이를 계산하는 프로그램을 짜달라고 부탁을 하였다.


입력형식

첫 번째 줄에는 N(1≤N≤200,000), F(1≤F≤25,000), M(1≤M≤200,000)이 주어진다. 

두 번째 줄에는 1번 시설의 특징이 주어지고, 그 다음 N-1개의 줄에는 k번 시설에서 래프팅 보트를 타면 가게 되는 다른 시설의 번호와 k번 시설의 특징이 주어진다. 

그 다음 M개의 줄에는 Ei와 Si가 주어지는데, Ei가 먼저 입력된다는 것에 유의해라.


출력형식

M개의 줄에 각각 Si번 시설에서 Ei번 시설로 가는 방법의 수를 출력한다.


입력 예

7 3 5
3
1 1
2 2
2 2
1 2
5 3
3 1
2 1
1 2
3 1
3 2
1 3

출력 예

1
2
2
3
0

Hint!



출처

IOI 2009

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP