Egy megye településeiről tudjuk, hogy bármely településről bármelyik másikra pontosan egy útvonalon lehet eljutni. Egy vállalat az összes településen nyit termelő üzemet. Tudjuk, hogy melyik településen van a raktár, ahova az egyes üzemek szállítanák az árut. Ismerjük, hogy melyik településen mennyi terméket gyárthatnak. Az egyes utakon egy nap maximum M mennyiségű termék szállítható. 

Írjunk programot, ami kiszámítja, hogy mekkorára kell építeni a raktárt, hogy a lehető legtöbb árut befogadja! 

Bemenet

A bemenet első sorában a települések N száma (1 <= N <= 10000), az utakon szállítható termékek maximális száma (1 <= M <= 100000) és a raktáros település R sorszáma (1 <= R <= N) van. A második sor pontosan N egész számot tartalmaz (egy-egy szóközzel elválasztva), az i. szám az i. településen gyártott áru mennyisége (1 <= mennyiség <= 1000). A következő N-1 sorban két egész szám van (egy-egy szóközzel elválasztva): két település sorszám, amelyek között út van (1 <= A ≠ B <= N).

Bemenet	Kimenet
10 200 2 100 100 50 50 50 100 200 100 50 50 1 2 3 4 4 5 4 2 2 6 6 7 6 8 8 9 10 8	550

A feladat forrása: NTOITV 2012 3.forduló, 9-10. évfolyam

Algoritmusok: 

megoldás