Tło zadania

To zadanie jest interaktywne.

Wielka uczona 欣 zamierza zbudować silną sztuczną inteligencję 隆, aby rządzić światem. Po wprowadzeniu kilku wietnamskich zadań z zawodów algorytmicznych jako zbioru treningowego odkryła, że 隆 samodzielnie wygenerowała nowe zadanie i podała jego rozwiązanie. Ponadto 隆 sprowadziła do tego zadania 30% danych wejściowych ze zbioru testowego. 欣 szybko przepisała zadanie: Dane jest ukorzenione drzewo. Należy obsługiwać dwie operacje:

• obliczanie sumy elementów na ścieżce w drzewie;
• zmianę rodzica jednego wierzchołka na inny wierzchołek.

„To zadanie nie wydaje się aż tak potężne. Dlaczego pozwala rozwiązać 30% zadań ze zbioru testowego?” — pomyślała 欣. Zanim zamknęła stronę z wynikami treningu, nagle zauważyła, że w zadaniu podanym przez 隆 koszt łączenia informacji nie wynosi $O(1)$. 欣 pogrążyła się w rozmyślaniach i stwierdziła, że nie umie rozwiązać tego zadania. Aby sprawdzić, jak trudne ono jest, przedstawia je Tobie.

Treść zadania

Należy utrzymywać drzewo o $n$ wierzchołkach, ukorzenione w wierzchołku $1$. Początkowo dla każdego $2 \le i \le n$ wierzchołek $i$ ma rodzica $p_i$ i zachodzi $p_i \lt i$.

Początkowo dysponujesz $n$ zbiorami $\{1\},\{2\},\cdots,\{n\} $. Dla dowolnych dwóch zbiorów $A$ i $B$, jeśli $A \cap B=\varnothing$, możesz jedną operacją, kosztem $|A|+|B|$, uzyskać zbiór $A \cup B$.

Następnie wykonywanych jest $q$ operacji. Każda z nich ma jeden z dwóch typów:

• 0 a b: niech $S$ oznacza zbiór wierzchołków na ścieżce od $a$ do $b$ w drzewie. Należy przedstawić $S$ jako $\cup_{i=1}^{k}A_i$, gdzie każdy $A_i$ jest wcześniej uzyskanym zbiorem oraz $\forall i \neq j,A_i \cap A_j=\varnothing$. Koszt odpowiedzi na zapytanie za pomocą $(A_1,A_2,\cdots,A_k) $ wynosi $k$.
• 1 a b: zmień rodzica wierzchołka $a$ na $b$. Gwarantowane jest $a \gt 1$ i to, że po zmianie te $n$ wierzchołków nadal tworzy drzewo, ale nie gwarantuje się $a \gt b$. Podczas tej operacji możesz tworzyć nowe zbiory na potrzeby przyszłych zapytań.

Niech $C_1$ będzie łącznym kosztem całego działania programu, a $C_2$ maksymalnym kosztem pojedynczej operacji. W każdym podzadaniu punkty są przyznawane według określonego sposobu zależnie od wartości $C_1,C_2$.

Szczegóły implementacji

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

Ten plik nagłówkowy definiuje typ infoset, służący do przechowywania uzyskanych zbiorów.

Typ ten ma metodę size(), zwracającą liczność zbioru. Nagłówek udostępnia również stałą emptyset, reprezentującą zbiór pusty.

Możesz ponadto wywoływać następujące funkcje:

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

• Tworzy nowy zbiór $A \cup B$, ponosząc odpowiedni koszt.
• Ten sam zbiór możesz tworzyć wielokrotnie, ale koszt naliczany jest za każdym razem.

void report(infoset A);

• Funkcję wolno wywoływać tylko podczas zapytania. Dodaje ona zbiór $A$ do końcowej sumy zbiorów, kosztem $1$.

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

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

• Możesz wstępnie przetworzyć informacje przed rozpoczęciem $q$ operacji.
• Koszt poniesiony w tej funkcji nie wlicza się do maksymalnego kosztu pojedynczej operacji, lecz wlicza się do łącznego kosztu całego działania programu.
• id oznacza numer podzadania, n liczbę wierzchołków, a q łączną liczbę operacji.
• dad ma rozmiar $n-1$, a dad[i] oznacza początkowego rodzica wierzchołka $i+2$.
• ve ma rozmiar $n$, a ve[i] oznacza początkowy zbiór $\{i+1\}$.

void modify(int x,int y);

• Wykonuje modyfikację: ustawia rodzica wierzchołka $x$ na wierzchołek $y$.

void ask(int x,int y);

• Wykonuje zapytanie o informacje na ścieżce od $x$ do $y$ w drzewie.
• Aby odpowiedzieć, należy kilkukrotnie wywołać report. Po zakończeniu tego zapytania biblioteka interaktywna sprawdzi, czy wszystkie zgłoszone zbiory $A$ spełniają warunki.

Podczas oceniania biblioteka interaktywna najpierw raz wywoła init, a następnie łącznie $q$ razy wywoła modify i ask.

Gwarantowane jest, że struktura drzewa i wykonywane operacje są w pełni ustalone przed rozpoczęciem interakcji i nie są tworzone dynamicznie na podstawie interakcji z Twoim programem. Operacje interaktywne są zatem deterministyczne i nie musisz interesować się szczegółami ich implementacji w bibliotece.

Podczas oceniania biblioteka korzysta ze specjalnej implementacji: pojedyncza zmienna typu infoset zawsze zajmuje $8$ bajtów pamięci. Zadbaj, aby podczas działania programu nie istniało jednocześnie zbyt wiele zmiennych tego typu.

Przy zachowaniu ograniczeń liczby wywołań czas działania biblioteki nie przekroczy 2 s, a jej własne zużycie pamięci nie przekroczy 16 MB.

Testowanie programu

Plik grader.cpp w załącznikach jest dostarczoną przez nas implementacją wzorcową biblioteki interaktywnej. Implementacja używana w ostatecznych testach jest inna, dlatego rozwiązanie nie powinno zależeć od implementacji biblioteki.

Aby uzyskać program wykonywalny, użyj polecenia: g++ grader.cpp long.cpp -o long -static -O2 -std=c++14

Dla skompilowanego programu:

• Program odczytuje ze standardowego wejścia dane w następującym formacie:
  • Pierwszy wiersz zawiera liczbę całkowitą $id$, oznaczającą numer podzadania.
  • Drugi wiersz zawiera dwie liczby całkowite $n,q$, oznaczające liczbę wierzchołków i łączną liczbę operacji.
  • Trzeci wiersz zawiera $n-1$ liczb całkowitych: numery rodziców wierzchołków od $2$ do $n$.
  • Następne $q$ wierszy zawiera po trzy liczby całkowite $op,x,y$, opisujące operację. $op=0$ oznacza zapytanie, a $op=1$ modyfikację.
• Po wczytaniu danych biblioteka dokładnie raz wywołuje init i $q$ razy modify lub ask, testując Twoje funkcje przy użyciu tych danych. Po prawidłowym wykonaniu program wypisze kilka wierszy; każdy zawiera liczby opisujące Twoją odpowiedź na dane zapytanie. Ostatni wiersz zawiera dwie liczby całkowite $W_1,W_2$, oznaczające odpowiednio łączny koszt działania programu i maksymalny koszt pojedynczej operacji.

Załączniki zawierają cztery zestawy plików przykładowych; czwarty spełnia szczególną własność podzadania drugiego. Przy testowaniu przykładów zignoruj porównanie ostatniego wiersza wyjścia, ponieważ biblioteka wypisuje w nim koszt działania programu, a nie odpowiedź na zapytanie.

Podzadania

Zadanie podlega najpierw takim samym ograniczeniom jak zadania tradycyjne. Na przykład błąd kompilacji daje $0$ punktów za całe zadanie, a błąd wykonania, przekroczenie czasu lub pamięci daje $0$ punktów za odpowiedni test. Wolno odwoływać się wyłącznie do zmiennych zdefiniowanych przez siebie lub udostępnionych przez bibliotekę oraz odpowiadających im obszarów pamięci. Próba dostępu do innych obszarów może spowodować błąd kompilacji lub wykonania.

Przy powyższych warunkach, jeśli w danym teście program wykona niedozwolone wywołanie funkcji, nie zakończy się poprawnie lub błędnie odpowie na zapytanie, otrzyma $0$ punktów za ten test. W przeciwnym przypadku stosuje się jeden z dwóch sposobów oceniania zależnie od poniesionych kosztów:

• Sposób pierwszy: jeśli $W_1 \gt 6 \cdot 10^8$, test otrzymuje $0$ punktów. W przeciwnym razie wynik wynosi $\frac{\frac{1.5 \cdot 10^8}{max(W_1,1.5 \cdot 10^8)} \cdot 7+3}{10}$ pomnożone przez liczbę punktów za podzadanie, do którego należy test.
• Sposób drugi: jeśli $W_2 \gt 2 \cdot 10^4$, test otrzymuje $0$ punktów. W przeciwnym razie wynik wynosi $\frac{5000}{max(W_2,5000)}$ pomnożone przez liczbę punktów za podzadanie, do którego należy test.

Różne podzadania korzystają z różnych sposobów oceniania. Wynik za podzadanie jest minimum wyników wszystkich należących do niego testów.

Ograniczenia

Dla wszystkich testów zachodzi $1 \le n,q \le 10^5$.

Szczególna własność: w każdej chwili każdy wierzchołek oprócz wierzchołka $1$ ma co najwyżej jedno dziecko.

Limit czasu: $10s$

Limit pamięci: $1024MB$

Posłowie

Gdy 欣 zauważyła, że po pięciu godzinach nadal nie rozwiązałeś zadania, była bardzo zadowolona z możliwości 隆. Jednak następnego ranka nagle odkryła, że dowód złożoności rozwiązania 隆 jest błędny.