Czech ACM Student Chapter

Czech Technical University in Prague

Charles University in Prague

Technical University of Ostrava

ˇ a

Slovak University of Technology

Pavol Jozef Saf´rik University in Koˇice

s

ˇ

University of Zilina

Masaryk University

Matej Bel University in Bansk´ Bystrica

a

University of West Bohemia

CTU Open Contest 2013

Frozen Rose-Heads

fr.c, fr.cpp, Fr.java

The winter is coming and all the experts are warning that it will be the coldest one in the last

hundred years. Freddy needs to make sure that his garden does not sustain any damage. One

of the most important tasks is to make sure that no water remains in his large watering system.

All the water comes from a central node and is distributed by pipes to neighboring nodes and so

on. Each node is either a sprinkler (rose head) with no outgoing pipe or an internal node with

one or more outgoing pipes leading to some other nodes. Every node has exactly one incoming

pipe, except for the central node which takes the water directly from a well and has no incoming

pipe. Every pipe has a valve that stops all the water going through the pipe. The valves are of

different quality and age, so some may be harder to close than others.

Freddy knows his valves well and has assigned a value to each pipe representing the amount of

effort needed to close the corresponding valve. He asks you to help him count the minimum

effort needed to close some valves so that no water goes to the sprinklers.

Input Specification

The input contains several test cases. Each test case starts with a line with two integers, the

number of nodes n (2 ≤ n ≤ 1 000), and the number of the central node c (1 ≤ c ≤ n). Each of

the next n - 1 lines represents one pipe and contains three integers, u, v (1 ≤ u, v ≤ n) and w

(1 ≤ w ≤ 1 000), where u and v are the nodes connected by a pipe and w is the effort needed

to close the valve on that pipe. You may assume that every node is reachable from the central

node.

Output Specification

For each test case, output a single line containing the minimum sum of efforts of valves to be

closed, such that the central node gets separated from all sprinklers.

Sample Input

Output for Sample Input

3

1

9

2

1

5

5

1

3

4

7

7

7

6

10

7

5

10

6

4

1

6

3

1

5

2

1

5

1

2

This problem was adapted from Stanford Local Contest