Dies ist eine interaktive Aufgabe.

Gegeben ist ein Fünftupel $(T,I,S_V,S_E,\iota)$ mit den folgenden Eigenschaften:

• $T=(V,E)$ ist ein gewurzelter Baum mit $n$ Knoten. $V$ ist seine Knotenmenge, $E$ seine Kantenmenge. Die Knoten sind mit $1,2,\ldots,n$ nummeriert; die Wurzel hat die Nummer $1$.
• $I$ ist eine Menge, deren Elemente Informationen heißen. Sie enthält zwei verschiedene besondere Elemente: das neutrale Element $\epsilon$ und die ungültige Information $\bot$.

Eine gewöhnliche Information besitzt zwei Eigenschaften: eine Knotenmenge und eine Kantenmenge. Das neutrale Element besitzt dagegen nur eine Kantenmenge, und die ungültige Information besitzt keine dieser beiden Eigenschaften.

• Für eine Information $o\in I\setminus\{\epsilon,\bot\}$ ist ihre Knotenmenge eine zweielementige Teilmenge von $V$, bezeichnet mit $S_V(o)$. Es gilt $S_V(o)\subseteq V$ und $|S_V(o)|=2$. Dabei ist die Differenz zweier Mengen $A,B$ als $A\setminus B=\{x\in A\mid x\notin B\}$ definiert.
• Für eine Information $o\in I\setminus\{\bot\}$ ist ihre Kantenmenge eine Teilmenge von $E$, bezeichnet mit $S_E(o)$, mit $S_E(o)\subseteq E$. Die Kantenmenge des neutralen Elements ist definitionsgemäß leer: $S_E(\epsilon)=\varnothing$.
• Zu jeder Kante $e=(u,v)\in E$ des Baums existiert eine Information $\iota(e)\in I$, deren Knotenmenge aus den Endpunkten und deren Kantenmenge aus der Kante selbst besteht: $S_V(\iota(e))=\{u,v\}$ und $S_E(\iota(e))=\{e\}$.

Informationen können auf zwei Arten zusammengeführt werden, bezeichnet mit $R$ und $C$. Für beliebige $a,b\in I$ seien $r=R(a,b)$ und $c=C(a,b)$ mit $r,c\in I$. Dann gilt:

• Die Zusammenführung des neutralen Elements mit einer beliebigen Information ergibt diese andere Information. Für $a=\epsilon$ gilt also $r=c=b$, und für $b=\epsilon$ gilt $r=c=a$.
• Die Zusammenführung der ungültigen Information mit einer beliebigen Information ergibt die ungültige Information. Für $a=\bot$ oder $b=\bot$ gilt also $r=c=\bot$.
• In allen verbleibenden Fällen ist das Ergebnis ungültig, wenn sich die Kantenmengen überschneiden oder der Schnitt der Knotenmengen nicht genau ein Element enthält. Gilt also $S_E(a)\cap S_E(b)\ne\varnothing$ oder $|S_V(a)\cap S_V(b)|\ne1$, so ist $r=c=\bot$.
• Andernfalls gilt:

$$S_E(r)=S_E(c)=S_E(a)\cup S_E(b),$$

$$S_V(r)=S_V(a),$$

$$S_V(c)=S_V(a)\oplus S_V(b).$$

Dabei bezeichnet $\oplus$ die symmetrische Differenz von Mengen, also $A\oplus B=(A\cup B)\setminus(A\cap B)$.

Der Abstand zweier Knoten in $T$ ist die Anzahl der Kanten auf dem eindeutigen einfachen Pfad zwischen ihnen.

Gegeben sind ein Bewertungsparameter $M$ und $q$ Anfragen. Jede Anfrage gibt einen Knoten $u$ und eine nichtnegative ganze Zahl $d$ vor. Sei $X$ die Menge aller Knoten von $T$, deren Abstand von $u$ höchstens $d$ ist. Sei außerdem $Y=\{(a,b)\in E\mid a,b\in X\}$ die Menge der Kanten innerhalb von $X$. Man kann beweisen, dass sich ausgehend von $\epsilon$ und allen $\iota(e)$ für $e\in E$ durch endlich viele Aufrufe von $R,C$ stets eine Information $o\ne\bot$ mit $S_E(o)=Y$ gewinnen lässt.

Für jede Anfrage musst du eine solche Information $o$ konstruieren und dabei insgesamt höchstens $M$ Aufrufe von $R$ und $C$ verwenden. Insbesondere kannst du für $d=0$ direkt das neutrale Element $\epsilon$ zurückgeben.

Implementierungsdetails

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

Der Header count.h stellt Folgendes bereit:

1. Den Datentyp info für Informationen.
2. Die Konstante emptyinfo vom Typ info, die $\epsilon$ entspricht und direkt verwendet werden kann.
3. Die Definition und Implementierung der folgenden beiden Zusammenführungsfunktionen, die du direkt aufrufen kannst:

info MR(info a,info b);
info MC(info a,info b);

• Die beiden Funktionen geben die Informationen zu $R(a,b)$ beziehungsweise $C(a,b)$ zurück.

Du musst sicherstellen, dass das Ergebnis eines Aufrufs von $R(a,b)$ oder $C(a,b)$ nicht $\bot$ ist. Andernfalls kann sich das Programm ungewöhnlich verhalten.

1. Die Definition und Implementierung der folgenden Funktion zum Prüfen, ob eine Information das neutrale Element ist. Du kannst sie direkt aufrufen:

bool isempty(info a);

• Diese Funktion gibt genau dann wahr zurück, wenn $a$ das neutrale Element ist.

Weitere Implementierungsdetails findest du in der bereitgestellten Referenzbibliothek für die Interaktion.

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

void init(int T, int n, int q, vector<int> fa, vector<info> e, int
   M);

• $T$ ist die Testfallnummer, $n$ die Anzahl der Baumknoten, $q$ die Anzahl der Anfragen und $M$ der Bewertungsparameter der Testdatei.
• fa und e haben beide die Länge $n-1$. Für $0\le i<n-1$ sind $fa[i]$ und $i+2$ die Endpunkte der $i$-ten Kante $e_i$. e[i] ist das Element vom Typ info, das der in der Aufgabenstellung definierten Information $\iota(e_i)$ entspricht. Es ist garantiert, dass $fa[i]<i+2$ gilt.

info ask(int u, int d);

• Es wird eine Anfrage mit der in der Aufgabenstellung beschriebenen Bedeutung der Parameter gestellt. Gib am Ende der Funktion eine Information zurück, die die geforderten Bedingungen erfüllt.

Bei der endgültigen Bewertung ruft die Interaktionsbibliothek für jede Testdatei init genau einmal und anschließend ask genau $q$-mal auf. Sie verwendet eine besondere Implementierung, bei der eine Variable vom Typ info stets 12 Byte Speicher belegt. Dies unterscheidet sich von der bereitgestellten Referenzbibliothek. Damit dein Programm die Speichergrenze einhält, dürfen während der Ausführung nicht zu viele info-Variablen gleichzeitig existieren.

Es ist garantiert, dass die endgültige Interaktionsbibliothek bei Einhaltung der Aufrufgrenzen und ohne Aufrufe von isempty höchstens 0,6 Sekunden Laufzeit und selbst höchstens 16 MiB Speicher benötigt. Werden ausschließlich $10^8$ Aufrufe von isempty ausgeführt, benötigt die endgültige Interaktionsbibliothek garantiert höchstens 0,25 Sekunden.

Die bereitgestellten Dateien enthalten count.cpp als Beispielprogramm, auf dessen Grundlage du deine Lösung implementieren kannst. Außerdem gibt es die Sicherungsdatei count_backup.h, die garantiert mit count.h identisch ist.

Wie du dein Programm testen kannst

Im Aufgabenverzeichnis liegen die beiden Referenzimplementierungen der Interaktionsbibliothek grader.o und checker.o. Es sind linkbare Objektdateien, die aus zwei verschiedenen Bibliotheken kompiliert wurden. Die Bibliothek der endgültigen Bewertung unterscheidet sich von diesen Implementierungen. Daher darf deine Lösung weder von einer konkreten Implementierung der Interaktionsbibliothek noch von der konkreten Implementierung des Typs info in count.h abhängen.

Zum Linken musst du den bereitgestellten Header count.h anpassen. Wenn du count.cpp mit grader.o linkst, kommentiere Zeile 5 von count.h aus und behalte Zeile 4 bei. Für checker.o kommentiere entsprechend Zeile 4 aus und behalte Zeile 5 bei. Du darfst die Implementierung von count.h selbst anpassen, um verschiedene Programme zu kompilieren.

Anschließend kannst du im Aufgabenverzeichnis mit den folgenden Befehlen eine ausführbare Datei erzeugen:

g++ count.cpp -c -O2 -std=c++14 -lm && g++ count.o grader.o -o count
g++ count.cpp -c -O2 -std=c++14 -lm && g++ count.o checker.o -o count

Der erste Befehl kompiliert die aktuelle Datei count.cpp und linkt sie mit grader.o zur ausführbaren Datei count. Der zweite Befehl kompiliert count.cpp und linkt sie mit checker.o, ebenfalls zur ausführbaren Datei count.

Die auf diese Weise erzeugte ausführbare Datei count arbeitet wie folgt:

• Sie liest Daten im folgenden Format von der Standardeingabe:

  • Die erste Zeile enthält vier ganze Zahlen $id,n,q,M$: die Testfallnummer, die Knotenanzahl, die Anfrageanzahl und den Bewertungsparameter.
  • Die zweite Zeile enthält $n-1$ ganze Zahlen $p_2,p_3,\ldots,p_n$, die die Eltern der Knoten $2$ bis $n$ angeben. Beim lokalen Testen musst du für alle $i\in[2,n]$ sicherstellen, dass $p_i<i$ gilt.
  • Die folgenden $q$ Zeilen enthalten jeweils zwei ganze Zahlen $u,d$ und beschreiben eine Anfrage.

• Nach dem Einlesen führt die Interaktionsbibliothek den Test aus. Hält dein Programm die Bibliotheksbeschränkungen nicht ein, gibt sie eine entsprechende Fehlermeldung aus. Andernfalls ist die Ausgabe der gelinkten Datei wie folgt:

  • Insgesamt eine Zeile mit drei ganzen Zahlen $C_1,C_2,C_3$, wobei:

    • $C_1$ die Gesamtzahl der Aufrufe von Bibliotheksfunktionen in init ist.
    • $C_2$ die Gesamtzahl der Aufrufe von Bibliotheksfunktionen während der Programmausführung ist.
    • $C_3$ die maximale Anzahl der Aufrufe von Bibliotheksfunktionen innerhalb eines der $q$ Aufrufe von ask ist.
    • Bei allen drei Werten werden nur Aufrufe von MR und MC gezählt, keine Aufrufe von isempty.

• Die möglichen Prüfungen unterscheiden sich je nach gelinkter Datei:

  • grader.o: Prüft während der Ausführung nicht, ob die von ask zurückgegebene Information korrekt ist, kann aber prüfen helfen, ob die Interaktionsoperationen den Anforderungen entsprechen. Seine Laufzeit kommt der Bibliothek der endgültigen Bewertung am nächsten. Du kannst damit die Geschwindigkeit testen, die Korrektheit wird jedoch nicht garantiert.
  • checker.o: Prüft während der Ausführung, ob die von ask zurückgegebene Information korrekt ist, und kann außerdem prüfen helfen, ob die Interaktionsoperationen den Anforderungen entsprechen. Zugleich prüft es, ob die von ask zurückgegebene Information korrekt ist. Dieses Programm ermöglicht also die Prüfung der Antwortkorrektheit.

Beim Testen musst du sicherstellen, dass die Eingabe der ausführbaren Datei count dem obigen Format entspricht. Andernfalls wird kein korrektes Ergebnis garantiert.

Beispiele

Beispiel 1

Siehe count/count1.in und count/count1.ans im Teilnehmerverzeichnis.

Beispiel 2

Siehe count/count2.in und count/count2.ans im Teilnehmerverzeichnis.

Dieses Beispiel erfüllt die besondere Eigenschaft A aus den Beschränkungen.

Beispiel 3

Siehe count/count3.in und count/count3.ans im Teilnehmerverzeichnis.

Dieses Beispiel erfüllt die besondere Eigenschaft B aus den Beschränkungen.

Beispiel 4

Siehe count/count4.in und count/count4.ans im Teilnehmerverzeichnis.

Teilaufgaben

Bei der endgültigen Bewertung wird nur count.cpp übernommen. Änderungen anderer Dateien im Teilnehmerverzeichnis beeinflussen die Bewertung nicht. Beachte:

• Eine nicht initialisierte Variable vom Typ info ist nicht notwendigerweise emptyinfo.
• Versuche nicht, auf Membervariablen des Typs info zuzugreifen oder sie zu ändern. Dies gilt andernfalls als Angriff auf die Interaktionsbibliothek.
• Rufe MR und MC nicht vor dem Aufruf von init auf. Andernfalls kann undefiniertes Verhalten auftreten.
• Du darfst nur auf selbst definierte Variablen und von der Bibliothek zurückgegebene info-Variablen zugreifen. Der Zugriff auf andere Speicherbereiche kann zu Kompilier- oder Laufzeitfehlern führen.

Zunächst gelten für diese Aufgabe dieselben Beschränkungen wie für gewöhnliche Aufgaben. Beispielsweise ergibt ein Kompilierfehler 0 Punkte für die gesamte Aufgabe; Laufzeitfehler sowie Überschreitungen der Zeit- oder Speichergrenze ergeben 0 Punkte für den jeweiligen Testfall.

Darüber hinaus erhält eine Testdatei 0 Punkte, wenn das Programm einen ungültigen Funktionsaufruf ausführt oder eine Anfrage falsch beantwortet. Andernfalls seien $C_1$ die Anzahl der Aufrufe von Bibliotheksfunktionen in init und $C_3$ die maximale Anzahl solcher Aufrufe in einem der insgesamt $q$ Aufrufe von ask. Gilt $C_1\le3\cdot10^7$ und überschreitet $C_3$ den Bewertungsparameter $M$ der Testdatei nicht, erhältst du ihre Punkte; andernfalls erhältst du sie nicht. Beachte: Für $C_1,C_3$ zählen nur Aufrufe von MR und MC, keine Aufrufe von isempty.

Beschränkungen

Für alle Testfälle gilt $1\le n\le2\cdot10^5$, $1\le q\le10^6$. In jeder Anfrage gilt $1\le u\le n$, $1\le d\le n-1$.

Besondere Eigenschaft A: Für alle $i\in[1,n-1]$ hat Knoten $i+1$ garantiert den Elternknoten $i$.

Besondere Eigenschaft B: Alle Anfragen erfüllen garantiert $u=1$.

Besondere Eigenschaft C: Alle Anfragen erfüllen garantiert $d\le100$.

Besondere Eigenschaft D: Alle Anfragen erfüllen garantiert $d\ge1000$.