35ος ΠΔΠ Γ' Φάση
Εσωτερικές Διαμάχες (conflicts)

Βρισκόμαστε στο έτος 338 π.Χ. Ο Φίλιππος Β’ ο Μακεδών, πατέρας του Μεγάλου Αλεξάνδρου, βρίσκεται στο Συνέδριο της Κορίνθου, όπου ηγείται της προσπάθειας για την ίδρυση μιας ομοσπονδίας ελληνικών κρατών.

Με όπλο του την ξακουστή μακεδονική φάλαγγα δεν έχει αμφιβολία για τις επιτυχίες των Ελλήνων στο πεδίο των μαχών. Αν κάτι τον ανησυχεί, αυτό είναι οι εσωτερικές διαταραχές. Προτού λοιπόν ξεκινήσει να καταστρώνει σχέδια, θέλει να ξέρει πόσα ζεύγη στρατιωτών μπορεί να βρεθούν σε διαμάχη.

Το σύστημα οργάνωσης του στρατού έχει ως εξής:

• Υπάρχουν \(N\) στρατιώτες, καθένας απ’ τους οποίους προσδιορίζεται με ένα μοναδικό φυσικό αριθμό μεταξύ \(1\) και \(N\).
• Ο Φίλιππος έχει τον αριθμό \(1\) και δεν έχει κανέναν άμεσα ανώτερό του.
• Κάθε άλλος στρατιώτης \(u\) έχει ακριβώς έναν άμεσα ανώτερό του \(p_u\) (\(p_u < u\)).

Λέμε ότι ο \(u\) είναι “ανώτερος” του \(v\) εάν ο \(u\) είναι ίσος με τον \(v\) ή αν ο \(u\) είναι ανώτερος του \(p_v\). Αν ο \(u\) είναι ανώτερος του \(v\), λέμε επίσης ότι ο \(v\) είναι “κατώτερος” του \(u\). (Προσέξτε ότι, με αυτούς τους ορισμούς, ένας στρατιώτης θεωρείται συγχρόνως ανώτερος και κατώτερος του εαυτού του.) Προφανώς, ο Φίλιππος είναι ανώτερος όλων.

Επιπλέον, ο κάθε στρατιώτης έχει μία δύναμη \(f_u\). Μπορεί μάλιστα η δύναμή του να είναι και αρνητική, σε περίπτωση που η παρουσία του στη μάχη θα προκαλούσε περισσότερο κακό παρά καλό.

Η ισχύς ενός στρατιώτη είναι το άθροισμα των δυνάμεων όλων των κατωτέρων του.

Ο Φίλιππος, ως έμπειρος στρατηγός, έχει παρατηρήσει ότι η μόνη περίπτωση δύο στρατιώτες \(u\) και \(v\) να έρθουν σε διαμάχη είναι:

• να έχουν ακριβώς ίση ισχύ, και επιπλέον
• να μην είναι ο ένας ανώτερος του άλλου.

Αναθέτει λοιπόν στον πιστό του σωματοφύλακα, τον Παυσανία του Ορέστη, μία αποστολή. Θα πρέπει να του αναφέρει για κάθε στρατιώτη το πλήθος των στρατιωτών με τους οποίους είναι πιθανό να έρθει σε διαμάχη.

Πρόβλημα:

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

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

Το αρχείο εισόδου με όνομα conflicts.in είναι αρχείο κειμένου με την εξής δομή. Η πρώτη γραμμή έχει δύο ακέραιους αριθμούς χωρισμένους μεταξύ τους με ένα κενό: το συνολικό πλήθος \(N\) όλων των μελών του στρατού, και τη δύναμη του Φιλίππου. Ακολουθούν \(N−1\) γραμμές που αντιστοιχούν κατά σειρά στα μέλη \(u\) πλήν του Φιλίππου (\(2 \leq u \leq N\)). Η \(i\)-οστή γραμμή περιέχει δύο ακέραιους αριθμούς χωρισμένους μεταξύ τους με ένα κενό διάστημα: τον άμεσα ανώτερο \(p_{i+1}\) και τη δύναμη \(f_{i+1}\) του στρατιώτη \(i+1\).

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

Το αρχείο εξόδου με όνομα conflicts.out είναι αρχείο κειμένου που περιέχει \(N\) γραμμές με έναν ακέραιο αριθμό η κάθε μία: η \(i\)-οστή γραμμή περιέχει το πλήθος μελών του στρατού με τα οποία ο στρατιώτης \(i\) μπορεί να έρθει σε διαμάχη.

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

conflicts.in	conflicts.out
10 8 1 -8 1 9 1 -1 3 -3 2 -4 3 -9 5 3 6 5 8 1	0 0 1 0 1 3 0 0 0 1

(Στο σχήμα, κάθε κύκλος παριστάνει ένα στρατιώτη. Ο πρώτος αριθμός είναι ο αριθμός του στρατιώτη, από \(1\) μέχρι \(N\), και ο δεύτερος είναι η δύναμή του.)

Εξήγηση: Ας εξετάσουμε τον στρατιώτη \(5\): Έχει ισχύ \(-3+3+1=1\), όπως και οι στρατιώτες \(1\), \(3\), \(6\), \(10\). Όμως ο \(1\) και ο \(3\) είναι ανώτεροι του \(5\), και ο \(10\) κατώτερός του. Επομένως η μόνη πιθανή διαμάχη του \(5\) είναι με τον στρατιώτη \(6\).

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

• \(1 \leq N \leq 100.000\)
  
• Για κάθε στρατιώτη \(u\) πλην του Φιλίππου θα είναι \(1 \leq p_u < u\).
• Για κάθε στρατιώτη \(u\) θα είναι \(-100 \leq f_u \leq 100\).
• Για περιπτώσεις ελέγχου συνολικής αξίας 10%, θα είναι \(1 \leq N \leq 1.000\).
• Για περιπτώσεις ελέγχου συνολικής αξίας 20%, κανένας στρατιώτης δε θα έχει περισσότερους από \(50\) ανώτερους.
• Για περιπτώσεις ελέγχου συνολικής αξίας 30%, το πλήθος ζευγών με ίδια ισχύ θα είναι το πολύ \(2.000.000\).

Προσοχή:

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

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