34858번 - shake!마을 방황하기

문제

shake!마을은 $N$개의 교차로와 $N-1$개의 양방향 도로로 이루어져 있는 트리 형태의 마을이다. 당신은 처음에 1ドル$번 교차로에 위치해 있으며 $M$분동안 $Q$번의 지시에 따라야 한다.

각 지시는 $i$분에 주어지며 $j$번 교차로로 이동하라는 내용이다. 또한 각 지시가 주어지는 시점은 전부 다르다. 지시를 받으면 즉시 목적지인 교차로를 향해 최단경로로 이동을 시작해야 하며 이전 지시를 끝마치지 않은 상황에서 새 지시가 주어진다면 이전 지시를 무시하고 새로 주어진 지시에 따라 새로운 목적지로 이동을 시작해야 한다. 그러나 shake!마을의 도로들은 중앙분리대로 각 방향이 구분되어 있기 때문에 안전상의 이유로 교차로가 아닌 도로 위에서 방향을 바꾸는 것이 불가능하다. 따라서 도로 위를 지나는중에 새로운 지시를 받으면 우선 가고 있던 방향으로 다음 교차로를 만날 때까지 이동한 후 가장 최근의 지시를 이행해야 한다. 이때 교차로에 도착하는 것과 동시에 새로운 지시가 주어진다면 그 지시를 따른다.

총 $M$분 중 몇 분 동안 도로를 따라 움직이지 않고 가만히 교차로에서 휴식을 취했는지를 구하여라.

입력

첫째 줄에 $N$과 $M,ドル $Q$가 주어진다. (1ドル \leq N, Q \leq 10^{5};$ $Q \leq M \leq 10^{5}$)

둘째 줄부터 $N-1$개의 줄에 걸쳐 도로에 대한 정보 $u$ $v$ $d$가 주어진다. 이는 $u$번 교차로와 $v$번 교차로를 잇는 도로가 존재하고 이를 지나는데 $d$분이 걸린다는 의미이다. (1ドル \leq u, v \leq N;$ 1ドル \leq d \leq 10^{5}$)

이후 $Q$개의 줄에 이동 지시들이 주어지는 시점을 기준으로 오름차순으로 정렬되어 $i$ $j$ 의 형태로 주어진다. (0ドル \leq i < M;$ 1ドル \leq j \leq N$)

모든 입력은 정수이다.

출력

휴식을 취한 총 시간을 출력하라.

제한

노트