28ος ΠΔΠ Γ' Φάση
Δίκτυο σχολείων (schoolnet)

Το Υπουργείο Παιδείας έχει συνδέσει τα \(N\) σχολεία της μέσης εκπαίδευσης σε ένα δίκτυο, που αποτελείται από \(N−1\) γραμμές επικοινωνίας. Κάθε γραμμή συνδέει δύο σχολεία, με τέτοιο τρόπο ώστε να είναι εφικτή η επικοινωνία οποιουδήποτε ζεύγους σχολείων, είτε άμεσα (μέσω μίας σύνδεσης) είτε έμμεσα (μέσω περισσότερων).

Το δίκτυο των σχολείων κινδυνεύει να διακοπεί αν δυσλειτουργεί έστω και μία από τις γραμμές επικοινωνίας. Για να ελέγχει την ποιότητα των γραμμών επικοινωνίας και να μπορεί να επεμβαίνει για την έγκαιρη επισκευή τους, το Υπουργείο προτίθεται να προμηθευτεί συσκευές ελέγχου και να τις τοποθετήσει σε κόμβους του δικτύου. Κάθε τέτοια συσκευή θα μπορεί να ελέγχει από τον κόμβο του δικτύου όπου έχει τοποθετηθεί όλες τις γραμμές επικοινωνίας με τις οποίες είναι συνδεδεμένος αυτός ο κόμβος.

Οι συσκευές αυτές είναι ακριβές, όπως επίσης και η τοποθέτησή τους, που μπορεί να κοστίζει περισσότερο ή λιγότερο, ανάλογα με τη θέση του σχολείου. Το Υπουργείο ενδιαφέρεται να περιορίσει το συνολικό κόστος, τοποθετώντας κατάλληλα τις συσκευές. Καλείστε να βρείτε ποιο είναι το ελάχιστο κόστος που απαιτείται για να τοποθετηθούν συσκευές που να ελέγχουν όλες οι γραμμές.

Πρόβλημα

Αρχεία εισόδου

Το αρχείο εισόδου με όνομα schoolnet.in είναι αρχείο κειμένου. Η πρώτη γραμμή του που περιέχει έναν μόνο ακέραιο αριθμό \(N\), το πλήθος των σχολείων που αποτελούν τους κόμβους του δικτύου. Έστω ότι τα σχολεία είναι αριθμημένα από \(1\) έως \(N\). Η δεύτερη γραμμή περιέχει ακριβώς \(N\) ακέραιους αριθμούς, χωρισμένους ανά δύο με ένα κενό διάστημα: το κόστος τοποθέτησης μίας συσκευής για κάθε σχολείο, κατά σειρά. Κάθε μία από τις επόμενες \(N−1\) γραμμές περιέχει ακριβώς δύο ακέραιους αριθμούς \(A\) και \(B\), χωρισμένους με ένα κενό διάστημα, όπου \(1 \le A, B \le N\) και \(A \ne B\). Αυτό σημαίνει ότι στο δίκτυο υπάρχει μία γραμμή επικοινωνίας που συνδέει απευθείας το σχολείο \(A\) με το σχολείο \(B\). Θεωρήστε δεδομένο ότι στο δίκτυο των σχολείων που περιγράφεται στο αρχείο εισόδου θα είναι δυνατή η επικοινωνία (άμεση ή έμμεση) μεταξύ οποιωνδήποτε δύο σχολείων.

Αρχεία εξόδου

Το αρχείο εξόδου με όνομα schoolnet.out είναι αρχείο κειμένου αποτελούμενο από μία μόνο γραμμή που θα περιέχει έναν μόνο ακέραιο αριθμό: το ελάχιστο δυνατό κόστος για την τοποθέτηση συσκευών που να ελέγχουν όλες τις γραμμές επικοινωνίας του δικτύου.

Παράδειγμα αρχείων εισόδου - εξόδου

schoolnet.in	schoolnet.out
6 10 10 1 1 10 10 1 2 3 1 1 4 5 3 4 6	12

Εξήγηση: Το Υπουργείο μπορεί να τοποθετήσει συσκευές στα σχολεία με αριθμούς \(1\), \(3\) και \(4\), έτσι ώστε να ελέγχονται όλες οι γραμμές επικοινωνίας. Το συνολικό κόστος τοποθέτησης των συσκευών είναι \(10+1+1=12\) και είναι το ελάχιστο δυνατό.

Όρια

Το συνολικό άθροισμα του κόστους τοποθέτησης για όλα τα σχολεία δε θα υπερβαίνει τα \(2\times 10^9\). Όλα τα κόστη θα είναι θετικά.

• Για περιπτώσεις ελέγχου συνολικής αξίας 20%, θα είναι: \(2 \le N \le 100\)
• Για περιπτώσεις ελέγχου συνολικής αξίας 100%, θα είναι: \(2 \le N \le 10^6\)

Μέγιστος χρόνος εκτέλεσης: 2 sec.
Μέγιστη διαθέσιμη μνήμη: 64 MB.