Zadanie z Grafami potrafię zrobić lepiej test niż zadanie wzorcowe (więc czegoś nie rozumiem)

Question

Mam takie zdanie: https://codeforces.com/problemset/problem/1466/D

I taką odpowiedź: https://codeforces.com/blog/entry/86126

Ale dla takiego grafu:

5
10 12 3 5 4
1 2
1 4
1 5
2 3

Potafię znaleźć rozwiązanie lepsze niż wzorcowe

Nigdzie w zadaniu nie mogę znaleźć że wierzołki jednego koloru muszą być spójne, dlaczego nie mogę zrobić tego tak jak pokazałęm na rysunku?

Answer 1

Wynik dla danego koloru to max z wyników dla wszystkich spójnych pokolorowanych danym kolorem. Czyli w tym drugim przypadku kolorem czerwonym rozbijasz graf i tworzysz dwie czarne spójne. W jednej czarnej spójnej wynikiem jest 19 a w drugiej 15, więc max z tego to 19 co daje wynik 19 + 22, czyli 41

Answer 2

Wynika to nie wprost z definicji tego, że w zadaniu masz informacje o tym, że jest to 'tree' czyli drzewo.

Z definicji wynika: W tym zadaniu otrzymujesz drzewo z n ważonymi wierzchołkami. Drzewo to połączony graf z n − 1n − 1 krawędziami.

 

Graf prosty G jest drzewem jedynie, jeśli spełnia jeden z warunków:

• dowolne dwa wierzchołki łączy dokładnie jedna ścieżka prosta.
• G jest acykliczny i dodanie krawędzi łączącej dowolne dwa wierzchołki utworzy cykl.
• G jest spójny i usunięcie dowolnej krawędzi spowoduje, że G przestanie być spójny