Este é um problema interativo.

A grande cientista 欣 pretende construir uma inteligência artificial forte chamada 隆 para dominar o mundo. Depois de fornecer alguns problemas vietnamitas de competições de algoritmos como conjunto de treinamento, ela descobriu que 隆 gerou automaticamente um novo problema e apresentou uma solução. Ao mesmo tempo, 隆 também reduziu a esse problema 30% dos dados de entrada do conjunto de testes.

欣 copiou imediatamente o problema, como segue:

Dada uma árvore enraizada, é necessário suportar dois tipos de operações:

• Consultar a soma dos elementos de um caminho na árvore.
• Alterar o pai de um vértice para outro vértice.

“Este problema não parece tão poderoso. Por que ele consegue resolver 30% dos problemas do conjunto de testes?”, pensou 欣.

Antes de fechar a página dos resultados do treinamento, 欣 percebeu de repente que, no problema proposto por 隆, o custo de combinar informações não era $O(1)$.

欣 ficou pensativa e percebeu que não sabia resolver o problema.

Para descobrir o quanto ele é difícil, 欣 colocou este problema diante de você.

Descrição

Você deve manter uma árvore enraizada no vértice $1$, com $n$ vértices. Inicialmente, para todo $2 \le i \le n$, o vértice $i$ tem um pai $p_i$, com a garantia de que $p_i \lt i$.

Inicialmente, você tem $n$ conjuntos $\{1\},\{2\},\cdots,\{n\} $. Para quaisquer dois conjuntos $A$ e $B$, se $A \cap B=\varnothing$, você pode obter o conjunto $A \cup B$ por meio de uma operação com custo $|A|+|B|$.

Em seguida, há $q$ operações. Cada operação é de um dos dois tipos:

• 0 a b: seja $S$ o conjunto dos vértices no caminho de $a$ a $b$ na árvore. Você deve representar $S$ como $\cup_{i=1}^{k}A_i$, onde cada $A_i$ é um conjunto que você já obteve e $\forall i \neq j,A_i \cap A_j=\varnothing$. O custo de responder a uma consulta com $(A_1,A_2,\cdots,A_k) $ é $k$.
• 1 a b: altera o pai do vértice $a$ para $b$. É garantido que $a \gt 1$ e que, após a alteração, os $n$ vértices ainda formam uma árvore, mas não é garantido que $a \gt b$. Durante esta operação, você pode gerar novos conjuntos para responder às consultas posteriores.

Sejam $C_1$ o custo total durante toda a execução do seu programa e $C_2$ o maior custo de uma única operação. Cada subtarefa atribui pontos de determinada maneira conforme os valores de $C_1,C_2$.

Detalhes de implementação

Certifique-se de que seu programa começa com #include "long.h".

O arquivo de cabeçalho define o tipo de dados infoset, usado para armazenar os conjuntos obtidos.

Esse tipo contém a função membro size(), que indica o tamanho do conjunto. O cabeçalho também fornece a constante emptyset, que representa o conjunto vazio.

Além disso, você pode chamar as seguintes funções:

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

• Gera um novo conjunto $A \cup B$ com determinado custo.
• Observe que você pode gerar o mesmo conjunto repetidamente, e o custo deve ser contabilizado a cada vez.

void report(infoset A);

• Você só pode chamar esta função durante uma operação de consulta. Ela indica que você deseja adicionar o conjunto $A$ à união final com custo $1$.

Você não precisa nem deve implementar a função principal. Você deve implementar as seguintes funções:

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

• Você pode pré-processar algumas informações antes do início das $q$ operações.
• O custo consumido nesta função não conta para o maior custo de uma única operação, mas conta para o custo total durante toda a execução do programa.
• id indica o número da subtarefa, n o número total de vértices e q o número total de operações.
• dad tem tamanho $n-1$, e dad[i] indica o pai inicial do vértice $i+2$.
• ve tem tamanho $n$, e ve[i] representa o conjunto inicial $\{i+1\}$.

void modify(int x,int y);

• Executa uma operação de alteração, definindo o vértice $y$ como pai do vértice $x$.

void ask(int x,int y);

• Executa uma operação de consulta às informações do caminho de $x$ a $y$ na árvore.
• Você deve chamar report algumas vezes para responder à consulta. Ao término desta consulta, a biblioteca de interação verificará se todos os conjuntos $A$ informados satisfazem as condições.

Durante a avaliação, a biblioteca de interação chama primeiro init uma vez e depois chama modify e ask um total de $q$ vezes.

Neste problema, a forma da árvore e as operações executadas são completamente determinadas antes do início da interação e não são construídas dinamicamente conforme a interação com seu programa. Portanto, as operações de interação do problema são determinísticas, e você não precisa se preocupar com sua implementação específica na biblioteca de interação.

Durante a avaliação, a biblioteca de interação usa uma implementação especial em que uma variável do tipo infoset sempre ocupa $8$ bytes de memória. Certifique-se de que não existam simultaneamente variáveis demais do tipo infoset durante a execução de seu programa.

É garantido que, respeitando o limite de chamadas, o tempo de execução da biblioteca de interação não excede 2 s, e a memória consumida pela própria biblioteca não excede 16 MB.

Como testar seu programa

O arquivo grader.cpp fornecido contém uma implementação de referência da biblioteca de interação. A implementação usada na avaliação final difere dessa referência; portanto, sua solução não deve depender da implementação da biblioteca de interação.

Você deve compilar o executável com o seguinte comando:

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

Para o executável compilado:

• O executável lê da entrada padrão dados no seguinte formato:
  • A primeira linha contém um inteiro $id$, que indica o número da subtarefa.
  • A segunda linha contém dois inteiros $n,q$, que indicam o número total de vértices e de operações.
  • A terceira linha contém $n-1$ inteiros, que indicam, respectivamente, os números dos pais dos vértices de $2$ a $n$.
  • As próximas $q$ linhas contêm três inteiros $op,x,y$ cada, descrevendo uma operação. $op=0$ indica uma consulta e $op=1$ indica uma alteração.
• Após a leitura, a biblioteca de interação chama exatamente uma vez init e $q$ vezes modify ou ask, usando os dados de entrada para testar suas funções. Depois de uma execução normal, o programa imprime várias linhas, cada uma com alguns números que representam sua resposta a uma consulta. A última linha contém dois inteiros $W_1,W_2$, que representam, respectivamente, o custo total da execução do seu programa e o maior custo de uma única operação.

Os arquivos fornecidos incluem quatro conjuntos de arquivos de exemplo, dos quais o quarto satisfaz a propriedade especial da subtarefa dois. Ao testar os exemplos, ignore a comparação da última linha do arquivo de saída, pois a última linha produzida pela biblioteca de interação representa o custo de execução do programa, e não o resultado de uma consulta.

Pontuação

Primeiro, este problema está sujeito às mesmas restrições de um problema tradicional. Por exemplo, um erro de compilação resulta em $0$ pontos para todo o problema; um erro de execução, a ultrapassagem do limite de tempo ou de memória, entre outros, resulta em $0$ pontos para o caso de teste correspondente. Você só pode acessar as variáveis definidas por você ou fornecidas pela biblioteca de interação e os respectivos espaços de memória. Tentar acessar outros espaços pode causar erros de compilação ou de execução.

Além das condições acima, em um caso de teste, se o programa fizer uma chamada de função ilegal, não terminar normalmente ou responder incorretamente a uma consulta, receberá $0$ pontos nesse caso. Caso contrário, há duas formas de pontuação, conforme o custo consumido pelo seu programa:

• Método de avaliação um: se $W_1 \gt 6 \cdot 10^8$, o caso de teste recebe $0$ pontos; caso contrário, sua pontuação é $\frac{\frac{1.5 \cdot 10^8}{max(W_1,1.5 \cdot 10^8)} \cdot 7+3}{10}$ multiplicado pela pontuação da subtarefa à qual pertence.
• Método de avaliação dois: se $W_2 \gt 2 \cdot 10^4$, o caso de teste recebe $0$ pontos; caso contrário, sua pontuação é $\frac{5000}{max(W_2,5000)}$ multiplicado pela pontuação da subtarefa à qual pertence.

Subtarefas diferentes usam métodos de avaliação diferentes. A pontuação de uma subtarefa é o mínimo das pontuações de todos os seus casos de teste.

Restrições

É garantido que, para todos os casos de teste, $1 \le n,q \le 10^5$.

Propriedade especial: em todo instante, cada vértice, exceto o vértice $1$, tem no máximo um filho.

Epílogo

Ao descobrir que você ainda não havia resolvido este problema após cinco horas, 欣 ficou muito satisfeita com a capacidade de 隆. No entanto, ao acordar na manhã seguinte, 欣 percebeu de repente que a prova da complexidade da abordagem de 隆 estava errada.