34ος ΠΔΠ Γ' Φάση
Φιλική Εταιρεία (filiki)

Βρισκόμαστε στην Οδησσό του 1814, και παρακολουθούμε την ίδρυση της Φιλικής Εταιρείας. Η προετοιμασία της επικείμενης επανάστασης απαιτεί απόλυτη μυστικότητα, κι έτσι οι Φιλικοί επινόησαν το εξής σύστημα:

Η Φιλική Εταιρεία αποτελείται από \(N\) μέλη.

Κάθε μέλος χρησιμοποιεί ως ψευδώνυμο έναν διαφορετικό ακέραιο αριθμό από το \(1\) ως το \(N\). Το αρχαιότερο μέλος (ας τον ονομάσουμε “Πρώτο”) χρησιμοποιεί το ψευδώνυμο \(1\).

Κάθε Φιλικός \(u\), εκτός του Πρώτου, έχει προσκληθεί στη Φιλική Εταιρεία από κάποιον αρχαιότερο Φιλικό \(p_u\). Προκειμένου να ενημερώνεται για τα νέα της Φιλικής Εταιρείας, ο \(u\) λαμβάνει κάθε φορά ένα κρυπτογραφημένο γράμμα από τον \(p_u\). Ο χρόνος που απαιτείται για να το αποκρυπτογραφήσει είναι \(t_u\) λεπτά.

Όταν κάποιο μυστικό πρέπει να διαδοθεί, για λόγους ασφάλειας ο Πρώτος το εκμυστηρεύεται αρχικά μόνο σε \(K−1\) άλλους Φιλικούς, έτσι ώστε συνολικά (μαζί με αυτόν) να το γνωρίζουν αρχικά \(K\). Αυτοί οι \(K\) (μαζί με τον Πρώτο) στέλνουν ταυτόχρονα γράμματα σε όσους Φιλικούς έχουν οι ίδιοι προσκαλέσει, οι οποίοι με τη σειρά τους αποκρυπτογραφούν το γράμμα που έλαβαν και κατόπιν το στέλνουν σε όσους εκείνοι έχουν προσκαλέσει, κ.ο.κ.

Με βάση το παραπάνω σύστημα μυστικότητας, ο Πρώτος σού ζητάει να σχεδιάσεις ένα πρόγραμμα που να επιλέγει βέλτιστα τους \(K−1\) Φιλικούς στους οποίους θα αποκαλύψει αρχικά το μυστικό, ώστε να ελαχιστοποιηθεί ο απαιτούμενος χρόνος μέχρι να γνωστοποιηθεί αυτό σε όλα τα μέλη, με την παραπάνω διαδικασία.

Πρόβλημα:

Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες της IOI (PASCAL, C, C++, Java) το οποίο θα διαβάζει τις τιμές των \(N\), \(K\), καθώς και τις τιμές των \(p_u\) και \(t_u\) για κάθε μέλος πλην του Πρώτου, και θα εκτυπώνει τον ελάχιστο δυνατό χρόνο στον οποίο μπορεί ένα μυστικό να γνωστοποιηθεί σε όλα τα μέλη.

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

Το αρχείο εισόδου με όνομα filiki.in είναι αρχείο κειμένου με την εξής δομή. Η πρώτη γραμμή έχει δύο ακέραιους αριθμούς χωρισμένους μεταξύ τους με ένα κενό: το συνολικό πλήθος \(N\) όλων των Φιλικών, και το πλήθος \(K\) των Φιλικών από τους οποίους ξεκινάει να διαδίδεται το μυστικό. Ακολουθούν \(N−1\) γραμμές που αντιστοιχούν κατά σειρά στα μέλη \(u\) πλήν του Πρώτου (\(2 \leq u \leq N\)). Κάθε τέτοια γραμμή περιέχει δύο ακέραιους αριθμούς χωρισμένους μεταξύ τους με ένα κενό διάστημα: το μέλος \(p_u\) που προσκάλεσε το μέλος \(u\) στη Φιλική Εταιρεία, και τον χρόνο \(t_u\) που χρειαζεται το μέλος \(u\) για να αποκρυπτογραφήσει ένα γράμμα.

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

Το αρχείο εξόδου με όνομα filiki.out είναι αρχείο κειμένου που περιέχει μία μόνο γραμμή με έναν ακέραιο αριθμό: τον ελάχιστο δυνατό χρόνο στον οποίο μπορεί ένα μυστικό να γνωστοποιηθεί σε όλα τα μέλη, αν ο Πρώτος επιλέξει τους \(K−1\) Φιλικούς με το βέλτιστο τρόπο.

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

1^o

filiki.in	filiki.out
5 2 1 50 1 10 3 25 4 20	50

Εξήγηση: Εδώ είναι \(K=2\), επομένως ο Πρώτος πρέπει να διαλέξει έναν ακόμα Φιλικό για να του γνωστοποιήσει αρχικά το μυστικό. Έστω ότι επιλέγει τον \(5\). Αμέσως ο \(1\) στέλνει το μυστικό σε αυτούς που προσκάλεσε (\(2\) και \(3\)), ενώ ο \(5\) δεν το στέλνει πουθενά αφού δεν προσκάλεσε κανέναν. Σε \(10\) λεπτά ο \(3\) έχει αποκρυπτογραφήσει το γράμμα και το προωθεί στον \(4\). Σε άλλα \(25\) λεπτά (συνεπώς στο λεπτό \(35\)) αποκρυπτογραφεί και ο \(4\) το γράμμα του. Τέλος, στο λεπτό \(50\), ο \(2\) αποκρυπτογραφεί το γράμμα που έλαβε από τον \(1\). Επομένως σε \(50\) λεπτά συνολικά όλοι γνωρίζουν το μυστικό. Δεν υπάρχει καλύτερη επιλογή που να οδηγεί σε μικρότερο συνολικό χρόνο.

2^o

filiki.in	filiki.out
5 3 1 50 1 10 3 25 4 20	20

Εξήγηση: Το ίδιο παράδειγμα με προηγουμένως, με τη διαφορά ότι τώρα \(K=3\). Αυτή τη φορά, ο Πρώτος μπορεί να επιλέξει τους \(2\) και \(4\). Ο \(3\) λαμβάνει γράμμα από τον \(1\), το οποίο αποκρυπτογραφεί σε \(10\) λεπτά, κι ο \(5\) λαμβάνει γράμμα από τον \(4\), το οποίο αποκρυπτογραφεί σε \(20\) λεπτά. Συνεπώς σε \(20\) λεπτά όλοι γνωρίζουν το μυστικό. Δεν υπάρχει καλύτερη επιλογή από αυτήν.

Περιορισμοί:

• \(1 \leq K \leq N ≤ 200.000\)
  
• Για κάθε Φιλικό \(u\) πλην του Πρώτου θα είναι \(1 \leq p_u < u\)
  
• \(1 \leq t_u \leq 100\)
  
• Για περιπτώσεις ελέγχου συνολικής αξίας 10%, θα είναι \(1 \leq N \leq 25\), και κανείς Φιλικός δε θα έχει προσκαλέσει παραπάνω από \(2\) μέλη.
  
• Για περιπτώσεις ελέγχου συνολικής αξίας 30%, θα είναι \(1 \leq N \leq 150\), και κανείς Φιλικός δε θα έχει προσκαλέσει παραπάνω από \(2\) μέλη.
  
• Για περιπτώσεις ελέγχου συνολικής αξίας 50%, θα είναι \(1 \leq N \leq 150\).
  

Προσοχή:

Φροντίστε να διαβάζετε την είσοδο και να εκτυπώνετε την έξοδο αποδοτικά, ειδικά αν προγραμματίζετε σε C++ ή Java.

Μορφοποίηση: Στην έξοδο, όλες οι γραμμές τερματίζουν με έναν χαρακτήρα newline.
Μέγιστος χρόνος εκτέλεσης: \(1\) sec.
Μέγιστη διαθέσιμη μνήμη: \(64\) MB.