양 구출 작전
면접 대비시간 제한1초메모리 제한256 MB
1번 섬을 루트로 하는 트리에서 각 정점에 양 또는 늑대 수가 주어집니다. 늑대 한 마리가 들어오는 양 한 마리만 잡아먹을 때 1번 섬에 도착하는 양의 최댓값을 구합니다.
문제
N개의 섬으로 이루어진 나라가 있습니다. 섬에는 1번 섬부터 N번 섬까지 번호가 붙어 있습니다.
1번 섬에는 구명보트만 있고, 다른 섬에는 양 또는 늑대가 살고 있습니다.
늘어나는 늑대의 개체 수를 감당할 수 없었던 양들은 구명보트를 타고 늑대가 없는 나라로 이주하기로 했습니다.
각 섬에서 1번 섬으로 가는 경로는 유일하며, i번 섬에는 p**i번 섬으로 가는 다리가 있습니다.
양들은 1번 섬으로 가는 경로를 따라 이동하고, 늑대들은 원래 있던 섬에서 움직이지 않고 섬으로 들어온 양들을 잡아먹습니다. 늑대는 날렵하기 때문에 섬에 들어온 양을 항상 잡을 수 있습니다. 그리고 늑대 한 마리는 최대 한 마리의 양만 잡아먹습니다.
얼마나 많은 양이 1번 섬에 도달할 수 있을까요?
입력
첫 번째 줄에 섬의 개수 N (2 ≤ N ≤ 123,456)이 주어집니다.
두 번째 줄부터 N-1개의 줄에 2번 섬부터 N번 섬까지 섬의 정보를 나타내는 ti, ai, pi (1 ≤ ai ≤ 109, 1 ≤ pi ≤ N)가 주어집니다.
ti가 'W'인 경우 i번 섬에 늑대가 ai마리 살고 있음을, ti가 'S'인 경우 i번 섬에 양이 ai마리 살고 있음을 의미합니다. pi는 i번째 섬에서 pi번 섬으로 갈 수 있는 다리가 있음을 의미합니다.
출력
첫 번째 줄에 구출할 수 있는 양의 수를 출력합니다.