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