37ος ΠΔΠ B' Φάση
Κυνήγι φιλοδωρημάτων (tiphunting)
Μετά τους καβγάδες του με τους ανταγωνιστές του στην προηγούμενη πόλη, ο Τάκης αναγκάστηκε να μετακομίσει. Η νέα πόλη του αποτελείται από \(N\) σπίτια και \(N-1\) δρόμους, καθένας εκ των οποίων συνδέει ένα ζεύγος σπιτιών. Η πόλη είναι κατασκευασμένη με τρόπο κατάλληλο ώστε το μονοπάτι μεταξύ οποιονδήποτε δύο πόλεων να υπάρχει και να είναι μοναδικό.
Η πιτσαρία του Τάκη έχει γίνει πασίγνωστη και δέχεται συνεχώς παραγγελίες, τις οποίες παραδίδει ο διανομέας του. Ο διανομέας γνωρίζει για κάθε δρόμο το κόστος της βενζίνης που χρειάζεται για να τον διασχίσει και για κάθε σπίτι το φιλοδώρημα που θα λάβει αν ολοκληρώσει μια παραγγελία σε αυτό. Συγκεκριμένα, το κόστος για να διασχίσει τον \(i\)-οστό δρόμο είναι \(w_i\), ενώ το φιλοδώρημα που δίνουν οι κάτοικοι του \(i\)-οστού σπιτιού είναι \(t_i\).
Ο Τάκης σκέφτεται να ανοίξει μία δεύτερη πιτσαρία, αλλά θέλει να είναι σε σημείο που θα εξυπηρετεί και τον διανομέα του, αφού θα χρειάζεται να μετακινείται συνεχώς. Για αυτό, σκέφτεται να του κάνει \(Q\) ανεξάρτητες ερωτήσεις της μορφής “Αν ξεκινήσεις μια διαδρομή από το σπίτι \(L\) και την τελειώσεις στο σπίτι \(R\), ποιο είναι το μέγιστο κέρδος που μπορείς να εξασφαλίσεις;”.
Ως διαδρομή ορίζουμε κάθε ακολουθία σπιτιών πεπερασμένου μήκους, της οποίας τα διαδοχικά σπίτια συνδέονται μεταξύ τους άμεσα από κάποιον δρόμο. Μια διαδρομή επιτρέπεται να περνάει από κάθε σπίτι όσες φορές θέλει ο διανομέας (ενδεχομένως καμία). Ο διανομέας λαμβάνει το φιλοδώρημα των σπιτιών της διαδρομής ακριβώς μία φορά (προσέξτε ότι στα ερωτήματα του Τάκη, αυτό συμπεριλαμβάνει πάντα τα φιλοδωρήματα των σπιτιών \(L\) και \(R\)), ενώ αντιθέτως χρεώνεται το κόστος των δρόμων της, δηλαδή το κόστος για να μεταβεί από κάθε σπίτι της διαδρομής στο επόμενο, κάθε φορά που τους διασχίζει. Το κέρδος μιας διαδρομής ισούται με τη διαφορά του αθροίσματος των φιλοδωρημάτων που θα προσφέρει στον διανομέα, μείον το συνολικό κόστος της βενζίνης που θα του κοστίσει.
Αυτές τις μέρες ο διανομέας βρίσκεται σε άδεια και επειδή ο Τάκης είναι βιαστικός, δεν μπορεί παρά να κάνει τις ερωτήσεις σε εσάς.
Μπορείτε να τις απαντήσετε ή θα χρειαστεί να περιμένει τον διανομέα να επιστρέψει;
Πρόβλημα:
Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες του ΠΔΠ (PASCAL, C, C++, Java) το οποίο θα διαβάζει τα δεδομένα εισόδου από το αρχείο tiphunting.in και θα εκτυπώνει τα αποτελέσματα στο αρχείο tiphunting.out.
Δεδομένα εισόδου (tiphunting.in):
Η πρώτη γραμμή περιέχει τον αριθμό του υποπροβλήματος (βλ. παρακάτω). Η δεύτερη γραμμή περιέχει δύο ακέραιους αριθμούς \(N\) και \(Q\), χωρισμένους μεταξύ τους με ένα κενό διάστημα: το πλήθος των σπιτιών της πόλης και το πλήθος των ερωτημάτων που θα ακολουθήσουν. Η τρίτη γραμμή αποτελείται από \(N\) ακέραιους αριθμούς \(t_1, t_2, \dots , t_N\), χωρισμένους ανά δύο με κενό διάστημα: τα φιλοδωρήματα που αφήνουν οι κάτοικοι των σπιτιών. Ακολουθούν \(N-1\) γραμμές καθεμία από τις οποίες περιέχει τρεις ακέραιους αριθμούς \(a_i\), \(b_i\) και \(w_i\), χωρισμένους ανά δύο με κενό διάστημα: τα δύο άκρα του \(i\)-οστού δρόμου και το κόστος διάσχισής του. Ακολουθούν \(Q\) γραμμές καθεμία από τις οποίες περιέχει δύο ακέραιους αριθμούς \(L_i\) και \(R_i\), χωρισμένους μεταξύ τους με κενό διάστημα: την αρχή και το τέλος της διαδρομής του \(i\)-οστού ερωτήματος.
Δεδομένα εξόδου (tiphunting.out):
Πρέπει να αποτελείται από \(Q\) γραμμές καθεμία εκ των οποίων να περιέχει ακριβώς έναν ακέραιο αριθμό: την απάντηση στο \(i\)-οστό ερώτημα, δηλαδή το μέγιστο κέρδος που μπορεί να πετύχει ο διανομέας αν επιλέξει κατάλληλη διαδρομή, ξεκινώντας από το σπίτι \(L_i\) και καταλήγοντας στο σπίτι \(R_i\).
Παράδειγμα εισόδου - εξόδου:
| tiphunting.in | tiphunting.out |
|---|---|
| 3 7 3 7 5 3 8 8 12 3 1 2 4 1 3 2 1 4 1 2 5 3 2 6 5 2 7 4 1 1 1 7 2 4 |
14 17 19 |
Εξήγηση: Για το πρώτο ερώτημα, ο διανομέας μπορεί να επιλέξει την διαδρομή 1 \(\rightarrow\) 4 \(\rightarrow\) 1 \(\rightarrow\) 2 \(\rightarrow\) 5 \(\rightarrow\) 2 \(\rightarrow\) 6 \(\rightarrow\) 2 \(\rightarrow\) 1. Με αυτόν τον τρόπο, θα λάβει φιλοδωρήματα συνολικής αξίας \(40\) (\(7+8+5+8+12\)), θα πληρώσει βενζίνη κόστους \(26\) (\(1+1+4+3+3+5+5+4\)) και θα έχει συνολικό κέρδος \(14\) (\(40-26\)). Παρατηρήστε ότι λαμβάνει τα φιλοδωρήματα των σπιτιών 1 και 2 ακριβώς μία φορά, παρόλο που διέρχεται από αυτά περισσότερες φορές.
Περιορισμοί:
- \(1\leq N\leq 200.000\).
- \(1\leq Q \leq 200.000\).
- \(0\leq t_i \leq 1.000.000.000\).
- \(1 \leq a_i, b_i \leq N\).
- \(0\leq w_i \leq 1.000.000.000\).
- \(1\leq L_i, R_i \leq N\).
Υποπροβλήματα:
- (8 βαθμοί) \(w_1= w_2=\cdots = w_{N-1} = 0\)
- (13 βαθμοί) \(N\leq 1.000, Q \leq 1.000, L_i= R_i\), για κάθε \(i\) (\(1\leq i\leq Q\))
- (10 βαθμοί) \(N\leq 1.000, Q\leq 1.000\)
- (23 βαθμοί) \(L_i =R_i\), για κάθε \(i\) (\(1\leq i\leq Q\))
- (21 βαθμοί) \(L_1 =L_2=\dots = L_Q\)
- (25 βαθμοί) Δεν υπάρχουν περαιτέρω περιορισμοί
Παρατηρήσεις:
Μορφοποίηση: Στην είσοδο αλλά και στην έξοδο, κάθε γραμμή τερματίζει με έναν χαρακτήρα newline.
Μέγιστος χρόνος εκτέλεσης: 2 sec.
Μέγιστη διαθέσιμη μνήμη: 128 MB.