To jest zadanie interaktywne.

Dany jest układ pięciu elementów $(T,I,S_V,S_E,\iota)$, gdzie:

• $T$ jest ukorzenionym drzewem o $n$ wierzchołkach, $T=(V,E)$, gdzie $V$ jest zbiorem wierzchołków, a $E$ zbiorem krawędzi drzewa $T$. Wierzchołki są ponumerowane $1,2,\ldots,n$, a korzeń ma numer $1$.
• $I$ jest zbiorem, którego elementy nazywamy informacjami. Są w nim dwa różne wyróżnione elementy: element neutralny $\epsilon$ oraz niepoprawna informacja $\bot$.

Zwykła informacja ma dwa atrybuty: zbiór wierzchołków i zbiór krawędzi. Element neutralny ma tylko atrybut zbioru krawędzi, a niepoprawna informacja nie ma żadnego z tych dwóch atrybutów.

• Dla informacji $o\in I\setminus\{\epsilon,\bot\}$ jej zbiór wierzchołków jest dwuelementowym podzbiorem $V$, oznaczanym $S_V(o)$, spełniającym $S_V(o)\subseteq V$ i $|S_V(o)|=2$. Różnicę dwóch zbiorów $A,B$ definiujemy jako $A\setminus B=\{x\in A\mid x\notin B\}$.
• Dla informacji $o\in I\setminus\{\bot\}$ jej zbiór krawędzi jest podzbiorem $E$, oznaczanym $S_E(o)$, spełniającym $S_E(o)\subseteq E$. Przyjmujemy, że zbiór krawędzi elementu neutralnego jest pusty, czyli $S_E(\epsilon)=\varnothing$.
• Dla dowolnej krawędzi drzewa $e\in E$, $e=(u,v)$, istnieje dotycząca jej informacja $\iota(e)\in I$, której zbiorem wierzchołków są końce krawędzi, a zbiorem krawędzi ona sama: $S_V(\iota(e))=\{u,v\}$, $S_E(\iota(e))=\{e\}$.

Informacje można łączyć na dwa sposoby, oznaczane przez $R$ i $C$. Dla dowolnych $a,b\in I$ oznaczmy $r=R(a,b)$, $c=C(a,b)$, przy czym $r,c\in I$. Wówczas:

• Połączenie elementu neutralnego z dowolną informacją daje tę drugą informację. Jeśli $a=\epsilon$, to $r=c=b$; jeśli $b=\epsilon$, to $r=c=a$.
• Połączenie niepoprawnej informacji z dowolną informacją daje niepoprawną informację. Jeśli $a=\bot$ lub $b=\bot$, to $r=c=\bot$.
• W pozostałych przypadkach, jeśli część wspólna zbiorów krawędzi obu informacji jest niepusta albo część wspólna ich zbiorów wierzchołków nie ma dokładnie jednego elementu, wynik połączenia jest niepoprawny. Jeśli $S_E(a)\cap S_E(b)\ne\varnothing$ lub $|S_V(a)\cap S_V(b)|\ne1$, to $r=c=\bot$.
• W przeciwnym razie:

$$ 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). $$

Tutaj $\oplus$ oznacza różnicę symetryczną zbiorów, czyli $A\oplus B=(A\cup B)\setminus(A\cap B)$.

Odległością dwóch wierzchołków w drzewie $T$ nazywamy liczbę krawędzi na jedynej ścieżce prostej między nimi.

Dany jest parametr punktacji $M$ oraz $q$ zapytań. Każde zapytanie podaje wierzchołek drzewa $u$ i nieujemną liczbę całkowitą $d$. Niech $X$ będzie zbiorem wszystkich wierzchołków $T$ w odległości nie większej niż $d$ od $u$, a $Y=\{(a,b)\in E\mid a,b\in X\}$ zbiorem krawędzi wewnątrz $X$. Można udowodnić, że zaczynając od $\epsilon$ i wszystkich $\iota(e)$ ($e\in E$), zawsze da się za pomocą skończonej liczby wywołań $R,C$ uzyskać informację $o\ne\bot$ taką, że $S_E(o)=Y$.

Dla każdego zapytania należy skonstruować taką informację $o$, wykonując łącznie nie więcej niż $M$ wywołań $R$ i $C$. W szczególności, jeśli $d=0$, wystarczy zwrócić element neutralny $\epsilon$.

Szczegóły implementacji

Upewnij się, że na początku programu znajduje się #include "count.h".

Plik nagłówkowy count.h zawiera następujące elementy:

1. Definicję typu danych info, odpowiadającego informacji.
2. Definicję stałej emptyinfo typu info, odpowiadającej $\epsilon$, której można bezpośrednio używać w programie.
3. Definicje i implementacje dwóch poniższych funkcji łączenia informacji, które można bezpośrednio wywoływać:

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

• Funkcje zwracają informacje odpowiadające odpowiednio $R(a,b)$ i $C(a,b)$.

Musisz zagwarantować, że wynik wywołania $R(a,b)$ lub $C(a,b)$ nie jest równy $\bot$; w przeciwnym razie program może zachowywać się nieprawidłowo.

1. Definicję i implementację funkcji sprawdzającej, czy informacja jest elementem neutralnym, którą można bezpośrednio wywoływać:

bool isempty(info a);

• Funkcja zwraca prawdę wtedy i tylko wtedy, gdy $a$ jest elementem neutralnym.

Więcej szczegółów implementacji można znaleźć w przykładowej bibliotece interaktywnej.

Nie musisz ani nie powinieneś implementować funkcji głównej. Należy zaimplementować następujące funkcje:

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

• T oznacza numer testu, n liczbę wierzchołków drzewa, q liczbę zapytań, a M parametr punktacji tego testu.
• Długości fa i e wynoszą $n-1$. Dla $0\le i<n-1$ wartości $fa[i]$ i $i+2$ są końcami $i$-tej krawędzi $e_i$, a e[i] jest elementem typu info, odpowiadającym $\iota(e_i)$ z treści zadania. Gwarantuje się, że $fa[i]<i+2$.

info ask(int u, int d);

• Podane jest zapytanie; parametry mają znaczenie opisane w treści zadania. Po zakończeniu funkcji należy zwrócić informację spełniającą warunki zadania.

Podczas właściwego oceniania biblioteka interaktywna w każdym teście wywoła init dokładnie raz, a następnie ask dokładnie $q$ razy. Biblioteka używa specjalnej implementacji, w której pojedyncza zmienna typu info zawsze zajmuje 12 bajtów pamięci; różni się to od udostępnionej biblioteki przykładowej. Aby zmieścić się w limicie pamięci, musisz zadbać, by podczas działania programu nie istniało zbyt wiele zmiennych typu info jednocześnie.

Gwarantuje się, że jeśli przestrzegane są limity wywołań i nie wywołuje się isempty, właściwa biblioteka interaktywna zużyje nie więcej niż 0,6 sekundy oraz nie więcej niż 16 MiB pamięci. Gwarantuje się także, że wykonanie samych $10^8$ wywołań isempty przez tę bibliotekę zajmie nie więcej niż 0,25 sekundy.

Wśród udostępnionych plików znajduje się przykładowy program count.cpp, który można rozbudować, rozwiązując to zadanie. Dołączono także plik zapasowy count_backup.h; gwarantujemy, że jest identyczny z count.h.

Testowanie programu

W katalogu zadania udostępniono dwie przykładowe implementacje biblioteki interaktywnej, grader.o i checker.o, będące plikami wynikowymi dwóch różnych bibliotek, które można dołączyć podczas linkowania. Biblioteka używana podczas właściwego oceniania ma inną implementację, więc rozwiązanie nie powinno zależeć od szczegółów implementacji biblioteki ani typu info w count.h.

Aby umożliwić linkowanie, należy zmodyfikować udostępniony count.h. Przy linkowaniu kodu count.cpp z grader.o zakomentuj w count.h wiersz 5 i pozostaw wiersz 4. Analogicznie, przy linkowaniu z checker.o zakomentuj wiersz 4 i pozostaw wiersz 5. Możesz samodzielnie zmieniać implementację count.h, aby kompilować różne programy.

Po zmianach można w katalogu zadania skompilować plik wykonywalny następującymi poleceniami:

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

Pierwsze polecenie kompiluje bieżący count.cpp, a następnie łączy go z grader.o, tworząc plik wykonywalny count. Drugie kompiluje bieżący count.cpp i łączy go z checker.o, również tworząc plik wykonywalny count.

Plik wykonywalny count skompilowany w powyższy sposób działa następująco:

• Wczytuje ze standardowego wejścia dane w poniższym formacie:

  • Pierwszy wiersz zawiera cztery liczby całkowite $id,n,q,M$: numer testu, liczbę wierzchołków drzewa, liczbę zapytań i parametr punktacji.
  • Drugi wiersz zawiera $n-1$ liczb całkowitych $p_2,p_3,\ldots,p_n$, oznaczających numery rodziców wierzchołków od $2$ do $n$. Podczas lokalnego debugowania musisz zapewnić, że $\forall i\in[2,n],\ p_i<i$.
  • Następnych $q$ wierszy zawiera po dwie liczby całkowite $u,d$, opisujące zapytanie.

• Po wczytaniu danych biblioteka przeprowadza test. Jeśli program nie spełnia wymagań biblioteki, na wyjściu pojawi się odpowiedni komunikat błędu. W przeciwnym razie dołączony plik wykonywalny wypisze:

  • Jeden wiersz zawierający trzy liczby całkowite $C_1,C_2,C_3$, gdzie:

    • $C_1$ jest łączną liczbą wywołań funkcji biblioteki w funkcji init.
    • $C_2$ jest łączną liczbą wywołań funkcji biblioteki podczas całego działania programu.
    • $C_3$ jest największą liczbą wywołań funkcji biblioteki w pojedynczym spośród $q$ wywołań ask.
    • Wszystkie trzy statystyki uwzględniają tylko wywołania MR i MC; wywołania isempty nie są liczone.

• Rodzaj możliwych kontroli zależy od dołączonego pliku:

  • grader.o: nie sprawdza podczas działania, czy informacja zwracana przez ask jest poprawna, ale pomaga sprawdzić zgodność operacji interaktywnych z wymaganiami. Jego czas działania jest najbliższy czasowi biblioteki używanej podczas oceniania, więc można go używać do pomiaru szybkości, lecz nie gwarantuje on poprawności programu.
  • checker.o: sprawdza podczas działania poprawność informacji zwracanej przez ask i pomaga sprawdzić zgodność operacji interaktywnych z wymaganiami. Sprawdza także poprawność informacji zwracanej przez ask. Ten program umożliwia kontrolę poprawności odpowiedzi.

Podczas debugowania musisz zapewnić, że dane przekazywane do pliku wykonywalnego count spełniają powyższy format wejścia; w przeciwnym razie poprawność wyników nie jest gwarantowana.

Przykład

Przykład 1

Zobacz pliki count/count1.in i count/count1.ans w katalogu zawodnika.

Przykład 2

Zobacz pliki count/count2.in i count/count2.ans w katalogu zawodnika.

Ten przykład spełnia szczególną własność A z ograniczeń danych.

Przykład 3

Zobacz pliki count/count3.in i count/count3.ans w katalogu zawodnika.

Ten przykład spełnia szczególną własność B z ograniczeń danych.

Przykład 4

Zobacz pliki count/count4.in i count/count4.ans w katalogu zawodnika.

Podzadania

Podczas właściwego oceniania pobierany jest tylko plik count.cpp. Zmiany innych plików w katalogu zawodnika nie wpływają na wynik. Uwaga:

• Niezainicjalizowana zmienna typu info nie musi być równa emptyinfo.
• Nie próbuj odczytywać ani zmieniać pól typu info; zostanie to uznane za atak na bibliotekę interaktywną.
• Nie wywołuj MR ani MC przed wywołaniem init, gdyż może to prowadzić do niezdefiniowanego zachowania.
• Możesz korzystać wyłącznie ze zdefiniowanych przez siebie zmiennych oraz zmiennych typu info zwróconych przez bibliotekę. Próby dostępu do innych obszarów pamięci mogą spowodować błąd kompilacji lub wykonania.

Obowiązują zwykłe ograniczenia, takie jak w zadaniach tradycyjnych: błąd kompilacji daje zero punktów za całe zadanie, a błąd wykonania, przekroczenie limitu czasu lub pamięci i podobne sytuacje dają zero punktów za odpowiedni test.

Ponadto niepoprawne wywołanie funkcji lub błędna odpowiedź na zapytanie daje zero punktów za dany test. W przeciwnym razie niech $C_1$ oznacza liczbę wywołań funkcji biblioteki w init, a $C_3$ największą liczbę wywołań funkcji biblioteki w pojedynczym spośród wszystkich $q$ wywołań ask. Jeśli $C_1\le3\cdot10^7$ i $C_3$ nie przekracza parametru punktacji $M$ tego testu, otrzymasz punkty za test; w przeciwnym razie ich nie otrzymasz. Uwaga: do $C_1,C_3$ wlicza się tylko wywołania MR i MC, a nie isempty.

Ograniczenia

Dla wszystkich testów $1\le n\le2\cdot10^5$, $1\le q\le10^6$; dla każdego zapytania $1\le u\le n$, $1\le d\le n-1$.

Szczególna własność A: dla każdego $i\in[1,n-1]$ rodzicem wierzchołka o numerze $i+1$ jest $i$.

Szczególna własność B: wszystkie zapytania spełniają $u=1$.

Szczególna własność C: wszystkie zapytania spełniają $d\le100$.

Szczególna własność D: wszystkie zapytania spełniają $d\ge1000$.