Skip to content
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
tests
README.html
README.md
RedRidingHood.cpp

README.md

Червената шапчица

Условие

Управителите на квартала на Червената шапчица си падат леко стиснати. Между всичките N дестинации в квартала са пострени само N - 1 пътеки, така че между всеки две места може да се стигне само по един начин.

На всяка дестинация има пари (късметчета, изпускани по земята). Червената шапчица е голям тарикат и иска да събере възможно най-много пари, за да може баба и да пазарува. Тя може да започне от където пожелае и да минава само по пътеките, събирайки парите на всяка дестинация. Това, което и пречи да събере всичко е, че ако мине по някоя пътека повече от веднъж, вълка ще я заподозре.

Помогнете на Червената шапчица да разбере колко най-много пари би могла да събере без да рискува да бъде изядена.

Вход

  • От първия ред се чете цяло число N
    • Броя дестинации в квартала
    • Дестинациите са номерирани от 1 до N
  • От втория ред се четат N числа разделени с интервали
    • Парите на всяка дестинация от 1 до N
  • От следващите N - 1 реда се четат по 2 числа
    • Пътека между 2 дестинации

Изход

  • Едно число на единствен ред
    • Максималните пари, които Червената шапчица може да събере

Ограничения

  • 2 <= N <= 100 000
  • Парите на всяко място са цяло число в интервала [ 0, 1000 ]
  • Лимит за памет: 16MiB
  • Лимит за време: 0.2 секунди

Примери

Вход

5
4 5 1 3 0
1 2
5 1
4 5
3 2

Изход

13

Пояснение

Може да се мине през всеки връх.
4+5+1+3+0 = 13

Вход

10
0 3 0 1 0 4 0 4 0 2
6 9
2 9
7 6
8 2
3 8
10 2
5 7
1 8
4 10

Изход

11

Пояснение

Един оптимален път е:
8 -> 2 -> 9 -> 6
You can’t perform that action at this time.