Dies ist eine interaktive Aufgabe.

Die große Wissenschaftlerin 欣 möchte eine starke künstliche Intelligenz namens 隆 bauen, um die Welt zu beherrschen. Nachdem sie einige vietnamesische Programmierwettbewerbsaufgaben als Trainingsmenge eingegeben hat, stellt sie fest, dass 隆 selbstständig eine neue Aufgabe erzeugt und eine Lösung dazu angegeben hat. Außerdem hat 隆 $30\%$ der Eingabedaten der Testmenge auf diese Aufgabe reduziert. 欣 schreibt die Aufgabe eilig wie folgt ab: Gegeben ist ein gewurzelter Baum. Zwei Operationen müssen unterstützt werden:

• Abfragen der Summe der Elemente auf einem Baumpfad;
• Ändern des Elternknotens eines Knotens zu einem anderen Knoten.

„Diese Aufgabe ist doch nicht besonders schwierig. Warum lassen sich damit $30\%$ der Aufgaben aus der Testmenge lösen?“, denkt 欣. Kurz bevor sie die Seite mit den Trainingsergebnissen schließt, bemerkt sie plötzlich, dass die Kosten für das Zusammenführen von Informationen in der von 隆 gestellten Aufgabe nicht $O(1)$ betragen. 欣 denkt lange nach und stellt fest, dass sie diese Aufgabe selbst nicht lösen kann. Um herauszufinden, wie schwierig sie ist, legt 欣 dir die Aufgabe vor.

Aufgabenstellung

Du musst einen Baum mit $n$ Knoten verwalten, dessen Wurzel der Knoten $1$ ist. Anfangs hat für alle $2 \le i \le n$ der Knoten $i$ den Elternknoten $p_i$, wobei $p_i \lt i$ garantiert ist.

Anfangs besitzt du die $n$ Mengen $\{1\},\{2\},\cdots,\{n\}$. Für zwei beliebige Mengen $A$ und $B$ mit $A \cap B=\varnothing$ kannst du durch eine Operation die Menge $A \cup B$ erhalten. Dies kostet $|A|+|B|$.

Danach folgen $q$ Operationen, jeweils von einem der folgenden beiden Typen:

• 0 a b: Sei $S$ die Menge der Knoten auf dem Pfad von $a$ nach $b$ im Baum. Du musst $S$ als $\cup_{i=1}^{k}A_i$ darstellen, wobei jede Menge $A_i$ bereits von dir erhalten worden sein muss und $\forall i \neq j,A_i \cap A_j=\varnothing$ gelten muss. Eine Anfrage mit $(A_1,A_2,\cdots,A_k)$ zu beantworten, kostet $k$.
• 1 a b: Ändere den Elternknoten von $a$ zu $b$. Es ist garantiert, dass $a \gt 1$ gilt und die $n$ Knoten nach der Änderung weiterhin einen Baum bilden, aber $a \gt b$ ist nicht garantiert. Während dieser Operation darfst du neue Mengen erzeugen, um spätere Anfragen zu beantworten.

Seien $C_1$ die Gesamtkosten während der gesamten Programmausführung und $C_2$ die maximalen Kosten einer einzelnen Operation. Jede Teilaufgabe wird nach einer bestimmten Regel anhand von $C_1,C_2$ bewertet.

Implementierungsdetails

Stelle sicher, dass dein Programm mit #include "long.h" beginnt.

Die Headerdatei definiert den Datentyp infoset, der die von dir erhaltenen Mengen speichert.

Dieser Typ besitzt die Mitgliedsfunktion size(), die die Größe einer Menge angibt. Die Headerdatei stellt außerdem die Konstante emptyset für die leere Menge bereit.

Zusätzlich kannst du folgende Funktionen aufrufen:

infoset merge(const infoset&A,const infoset&B);

• Erzeugt unter entsprechenden Kosten eine neue Menge $A \cup B$.
• Beachte, dass du dieselbe Menge mehrfach erzeugen darfst; die Kosten werden dabei jedes Mal erneut berechnet.

void report(infoset A);

• Du darfst diese Funktion nur während einer Anfrage aufrufen. Damit fügst du die Menge $A$ zur abschließenden Vereinigung hinzu, was $1$ kostet.

Du musst und sollst keine Hauptfunktion implementieren. Implementiere die folgenden Funktionen:

void init(int id,int n,int q,vector<int>dad,vector<infoset>ve);

• Du darfst vor Beginn der $q$ Operationen Informationen vorberechnen.
• Die in dieser Funktion entstehenden Kosten zählen nicht zu den maximalen Kosten einer einzelnen Operation, aber zu den Gesamtkosten während der gesamten Programmausführung.
• id ist die Nummer der Teilaufgabe, n die Anzahl der Knoten und q die Anzahl der Operationen.
• dad hat die Größe $n-1$; dad[i] gibt den anfänglichen Elternknoten von Knoten $i+2$ an.
• ve hat die Größe $n$; ve[i] stellt die anfängliche Menge $\{i+1\}$ dar.

void modify(int x,int y);

• Führt eine Änderung aus und setzt den Elternknoten von $x$ auf $y$.

void ask(int x,int y);

• Führt eine Anfrage nach den Informationen auf dem Baumpfad von $x$ nach $y$ aus.
• Du musst die Anfrage durch mehrere Aufrufe von report beantworten. Am Ende der Anfrage prüft die Interaktionsbibliothek, ob alle von dir gemeldeten Mengen $A$ die Bedingungen erfüllen.

Bei der Auswertung ruft die Interaktionsbibliothek zunächst einmal init und danach insgesamt $q$-mal modify oder ask auf.

Die Form des Baums und alle auszuführenden Operationen stehen bereits vor Beginn der Interaktion vollständig fest. Sie werden nicht während der Interaktion mit deinem Programm dynamisch erzeugt. Die interaktiven Operationen sind somit deterministisch; du musst dich nicht um ihre konkrete Implementierung in der Interaktionsbibliothek kümmern.

Bei der Auswertung verwendet die Interaktionsbibliothek eine spezielle Implementierung, bei der jede Variable vom Typ infoset stets $8$ Byte Speicher benötigt. Achte darauf, dass während der Programmausführung nicht zu viele Variablen dieses Typs gleichzeitig existieren.

Unter Einhaltung der Aufrufbeschränkungen benötigt die Interaktionsbibliothek höchstens 2 s Laufzeit und höchstens 16 MB Speicher.

Testen des Programms

Die bereitgestellte Datei grader.cpp ist eine Referenzimplementierung der Interaktionsbibliothek. Die bei der endgültigen Auswertung verwendete Implementierung unterscheidet sich davon; deine Lösung darf daher nicht von der Implementierung der Interaktionsbibliothek abhängen.

Mit folgendem Befehl kompilierst du das ausführbare Programm:

g++ grader.cpp long.cpp -o long -static -O2 -std=c++14

Für das so erzeugte Programm gilt:

• Es liest Daten in folgendem Format von der Standardeingabe:

  • Die erste Zeile enthält einen ganzzahligen Wert $id$, die Nummer der Teilaufgabe.
  • Die zweite Zeile enthält zwei ganze Zahlen $n,q$, die Anzahl der Knoten und der Operationen.
  • Die dritte Zeile enthält $n-1$ ganze Zahlen: die Nummern der Elternknoten der Knoten $2$ bis $n$.
  • Die folgenden $q$ Zeilen enthalten jeweils drei ganze Zahlen $op,x,y$, die eine Operation beschreiben. $op=0$ steht für eine Anfrage, $op=1$ für eine Änderung.
• Nach dem Einlesen ruft die Interaktionsbibliothek genau einmal init und insgesamt $q$-mal modify oder ask auf, um deine Funktionen mit den Eingabedaten zu testen. Bei normalem Ablauf gibt das Programm mehrere Zeilen mit Zahlen aus, die deine Antworten auf die einzelnen Anfragen darstellen. Die letzte Zeile enthält zwei ganze Zahlen $W_1,W_2$: die Gesamtkosten deiner Programmausführung und die maximalen Kosten einer einzelnen Operation.

Die bereitgestellten Dateien enthalten vier Beispiele; das vierte erfüllt die besondere Eigenschaft der zweiten Teilaufgabe. Ignoriere beim Testen der Beispiele den Vergleich der letzten Ausgabezeile, da die letzte von der Interaktionsbibliothek ausgegebene Zeile die Ausführungskosten und keine Anfrageantwort enthält.

Teilaufgaben

Zunächst gelten die üblichen Beschränkungen wie bei traditionellen Aufgaben. Beispielsweise führt ein Kompilierungsfehler zu $0$ Punkten für die gesamte Aufgabe. Laufzeitfehler oder Überschreitungen des Zeit- oder Speicherlimits führen zu $0$ Punkten für den jeweiligen Testfall. Du darfst nur auf selbst definierte oder von der Interaktionsbibliothek bereitgestellte Variablen und die zugehörigen Speicherbereiche zugreifen. Zugriffe auf andere Speicherbereiche können Kompilierungs- oder Laufzeitfehler verursachen.

Darüber hinaus erhält ein Testfall $0$ Punkte, wenn dein Programm unzulässige Funktionsaufrufe ausführt, nicht ordnungsgemäß beendet wird oder eine Anfrage falsch beantwortet. Andernfalls gibt es zwei Bewertungsverfahren, die von den Kosten deines Programms abhängen:

• Verfahren I: Falls $W_1 \gt 6 \cdot 10^8$, erhältst du für den Testfall $0$ Punkte. Andernfalls beträgt seine Punktzahl $\frac{\frac{1.5 \cdot 10^8}{\max(W_1,1.5 \cdot 10^8)} \cdot 7+3}{10}$ mal die Punktzahl der Teilaufgabe, zu der dieser Testfall gehört.
• Verfahren II: Falls $W_2 \gt 2 \cdot 10^4$, erhältst du für den Testfall $0$ Punkte. Andernfalls beträgt seine Punktzahl $\frac{5000}{\max(W_2,5000)}$ mal die Punktzahl der Teilaufgabe, zu der dieser Testfall gehört.

Für verschiedene Teilaufgaben werden unterschiedliche Bewertungsverfahren verwendet. Die Punktzahl einer Teilaufgabe ist das Minimum der Punktzahlen aller zugehörigen Testfälle.

Beschränkungen

Für alle Testfälle gilt $1 \le n,q \le 10^5$.

Besondere Eigenschaft: Zu jedem Zeitpunkt hat jeder Knoten außer Knoten $1$ höchstens ein Kind.

Nachwort

Als 欣 feststellt, dass du die Aufgabe auch nach fünf Stunden noch nicht gelöst hast, ist sie mit den Fähigkeiten von 隆 sehr zufrieden. Am nächsten Morgen bemerkt sie jedoch plötzlich, dass der Beweis für die Laufzeitkomplexität des Verfahrens von 隆 falsch ist.