Este é um problema interativo.

É dada uma quíntupla $(T,I,S_V,S_E,\iota)$, em que:

• $T$ é uma árvore enraizada com $n$ vértices, $T=(V,E)$, sendo $V$ o conjunto de vértices de $T$ e $E$ seu conjunto de arestas. Os vértices são numerados $1,2,\ldots,n$, e a raiz tem o número 1.
• $I$ é um conjunto cujos elementos são chamados de informações. Há dois elementos especiais distintos: o elemento neutro $\epsilon$ e a informação inválida $\bot$.

Em geral, cada informação possui dois atributos: um conjunto de vértices e um conjunto de arestas. Em particular, o elemento neutro possui apenas o atributo conjunto de arestas, e a informação inválida não possui nenhum desses dois atributos.

• Para uma informação $o\in I\setminus\{\epsilon,\bot\}$, seu conjunto de vértices é um subconjunto de $V$ com dois elementos, denotado por $S_V(o)$, satisfazendo $S_V(o)\subseteq V$ e $|S_V(o)|=2$. A diferença entre dois conjuntos $A,B$ é definida como $A\setminus B=\{x\in A\mid x\notin B\}$.
• Para uma informação $o\in I\setminus\{\bot\}$, seu conjunto de arestas é um subconjunto de $E$, denotado por $S_E(o)$, satisfazendo $S_E(o)\subseteq E$. O conjunto de arestas do elemento neutro é definido como vazio, isto é, $S_E(\epsilon)=\varnothing$.
• Para qualquer aresta $e\in E$ da árvore, escreva $e=(u,v)$. Existe uma informação $\iota(e)\in I$ associada a $e$, cujo conjunto de vértices contém seus extremos e cujo conjunto de arestas contém a própria aresta: $S_V(\iota(e))=\{u,v\}$ e $S_E(\iota(e))=\{e\}$.

Há duas formas de combinar informações, denotadas por $R$ e $C$. Para quaisquer $a,b\in I$, sejam $r=R(a,b)$ e $c=C(a,b)$, com $r,c\in I$. Então:

• Combinar o elemento neutro com qualquer informação resulta na outra informação. Isto é, se $a=\epsilon$, então $r=c=b$; se $b=\epsilon$, então $r=c=a$.
• Combinar a informação inválida com qualquer informação resulta na informação inválida. Isto é, se $a=\bot$ ou $b=\bot$, então $r=c=\bot$.
• Nos casos restantes, se a interseção dos conjuntos de arestas das duas informações não for vazia ou se a interseção dos conjuntos de vértices não tiver tamanho 1, a combinação resulta na informação inválida. Isto é, se $S_E(a)\cap S_E(b)\ne\varnothing$ ou $|S_V(a)\cap S_V(b)|\ne1$, então $r=c=\bot$.
• Caso contrário,

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

Aqui, $\oplus$ representa a diferença simétrica de conjuntos: $A\oplus B=(A\cup B)\setminus(A\cap B)$.

A distância entre dois vértices de $T$ é definida como o número de arestas no único caminho simples da árvore que tem esses dois vértices como extremos.

São dados um parâmetro de pontuação $M$ e $q$ consultas. Cada consulta fornece um vértice $u$ da árvore e um inteiro não negativo $d$. Seja $X$ o conjunto de todos os vértices de $T$ cuja distância até $u$ não excede $d$, e seja $Y=\{(a,b)\in E\mid a,b\in X\}$ o conjunto de arestas internas a $X$. Pode-se provar que, partindo de $\epsilon$ e de todas as informações $\iota(e)$ ($e\in E$), é sempre possível obter, com um número finito de chamadas a $R,C$, uma informação $o\ne\bot$ que satisfaz $S_E(o)=Y$.

Em cada consulta, você deve construir uma informação $o$ que satisfaça essa exigência, com a restrição de que o total de chamadas a $R$ e $C$ não exceda $M$. Em particular, se $d=0$, basta retornar diretamente o elemento neutro $\epsilon$.

Detalhes de implementação

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

O cabeçalho count.h implementa o seguinte:

1. Define o tipo de dados info, correspondente às informações.

2. Define a constante emptyinfo, do tipo info, correspondente a $\epsilon$. Você pode usá-la diretamente no programa.

3. Define e implementa as duas funções de combinação de informações abaixo, que você pode chamar diretamente:

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

• As duas funções retornam as informações correspondentes a $R(a,b)$ e $C(a,b)$, respectivamente.

Você deve garantir que o resultado de uma chamada a $R(a,b)$ ou $C(a,b)$ não seja $\bot$; caso contrário, o programa pode apresentar comportamento anormal.

1. Define e implementa uma função que verifica se uma informação é o elemento neutro, que você pode chamar diretamente:

bool isempty(info a);

• Essa função retorna verdadeiro se, e somente se, $a$ for o elemento neutro.

Você pode consultar a biblioteca de interação de referência para conhecer mais detalhes de implementação.

Você não precisa e não deve implementar a função principal. Deve implementar as funções a seguir:

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

• $T$ indica o número do teste, $n$ o número de vértices da árvore, $q$ o número de consultas e $M$ o parâmetro de pontuação desse teste.
• fa e e têm comprimento $n-1$. Para $0\le i<n-1$, fa[i] e $i+2$ são os dois extremos da $i$-ésima aresta $e_i$, e e[i] é o elemento do tipo info correspondente a $\iota(e_i)$ mencionado na descrição. É garantido que fa[i] é menor que $i+2$.

info ask(int u, int d);

• Recebe uma consulta, com os parâmetros definidos na descrição do problema. Ao terminar a função, você deve retornar uma informação que satisfaça as condições do problema.

Na avaliação final, em cada teste, a biblioteca de interação chamará init exatamente uma vez e depois chamará ask $q$ vezes. A biblioteca usará uma implementação especial na qual cada variável do tipo info ocupa sempre 12 bytes de memória; isso difere da biblioteca de interação de referência fornecida. Para manter o uso de memória dentro do limite do problema durante a execução, você deve garantir que não existam simultaneamente variáveis demais do tipo info.

É garantido que, respeitando o limite de chamadas e sem chamadas a isempty, o tempo de execução da biblioteca de interação da avaliação final não excede 0,6 segundo, e a memória consumida pela própria biblioteca não excede 16 MiB. Também é garantido que, executando apenas $10^8$ chamadas a isempty, o tempo de execução da biblioteca da avaliação final não excede 0,25 segundo.

Os arquivos fornecidos incluem count.cpp, um programa de exemplo que você pode usar como base para implementar sua solução. Também incluem um arquivo de cópia de segurança chamado count_backup.h, que é garantidamente idêntico a count.h.

Como testar o programa

O diretório deste problema fornece duas implementações de referência da biblioteca de interação, grader.o e checker.o, que são arquivos vinculáveis obtidos pela compilação de duas bibliotecas diferentes. A implementação usada na avaliação final é diferente dessas implementações. Portanto, sua solução não deve depender dos detalhes da implementação da biblioteca de interação, nem da implementação concreta do tipo info em count.h.

Você precisa modificar o arquivo count.h fornecido para permitir a vinculação. Especificamente, para vincular o código-fonte count.cpp com grader.o, comente a linha 5 de count.h e mantenha o código da linha 4. Para vincular com checker.o, faça o análogo: comente a linha 4 e mantenha o código da linha 5. Você pode modificar a implementação de count.h para permitir a compilação dos diferentes programas.

Após a alteração, use os seguintes comandos no diretório do problema para compilar o executável:

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

O primeiro comando compila o count.cpp atual e o vincula a grader.o, gerando o executável count. O segundo compila o count.cpp atual e o vincula a checker.o, também gerando o executável count.

O executável count compilado dessa forma funciona da seguinte maneira:

• O executável lê da entrada padrão dados no seguinte formato:

  • A primeira linha contém quatro inteiros $id,n,q,M$, que indicam, respectivamente, o número do teste, o número de vértices da árvore, o número de consultas e o parâmetro de pontuação.
  • A segunda linha contém $n-1$ inteiros $p_2,p_3,\ldots,p_n$, que indicam os números dos pais dos vértices de 2 a $n$. Durante a depuração local, você deve garantir que $\forall i\in[2,n],\ p_i<i$.
  • As próximas $q$ linhas contêm dois inteiros $u,d$ cada uma, descrevendo uma consulta.

• Após a leitura, a biblioteca de interação realiza os testes. Se seu programa não respeitar as restrições da biblioteca, ela emitirá a mensagem de erro correspondente na saída. Caso contrário, a saída do executável vinculado será a seguinte:

  • Uma única linha com três inteiros $C_1,C_2,C_3$, em que:

    • $C_1$ é o total de chamadas às funções da biblioteca de interação feitas pelo programa dentro de init.
    • $C_2$ é o total de chamadas às funções da biblioteca de interação durante toda a execução do programa.
    • $C_3$ é o maior número de chamadas às funções da biblioteca de interação em uma das $q$ chamadas de ask.
    • Para essas três estatísticas, contamos apenas as chamadas a MR e MC; as chamadas a isempty não são contadas.

• As verificações realizadas diferem conforme o arquivo vinculado. Especificamente:

  • grader.o: durante a execução, não verifica se a informação retornada por ask é correta, mas ajuda a verificar se as operações de interação satisfazem as exigências. Seu tempo de execução é o mais próximo do da biblioteca usada na avaliação. Assim, você pode usá-lo para testar a velocidade de execução, mas ele não garante a correção do programa.
  • checker.o: durante a execução, verifica se a informação retornada por ask é correta e também ajuda a verificar se as operações de interação satisfazem as exigências. Além disso, verifica se a informação retornada por ask é correta. Esse programa permite verificar a correção das respostas.

Durante a depuração, você deve garantir que os dados fornecidos ao executável count respeitem o formato acima; caso contrário, a correção da saída não é garantida.

Exemplos

Exemplo 1

Consulte count/count1.in e count/count1.ans no diretório do competidor.

Exemplo 2

Consulte count/count2.in e count/count2.ans no diretório do competidor.

Esse exemplo satisfaz a propriedade especial A das restrições.

Exemplo 3

Consulte count/count3.in e count/count3.ans no diretório do competidor.

Esse exemplo satisfaz a propriedade especial B das restrições.

Exemplo 4

Consulte count/count4.in e count/count4.ans no diretório do competidor.

Pontuação

Na avaliação final, apenas count.cpp será recolhido. Alterar outros arquivos do diretório do competidor não afetará o resultado da avaliação. Atenção:

• Não é garantido que uma variável do tipo info não inicializada seja igual a emptyinfo.
• Não tente acessar ou alterar os membros do tipo info; isso será considerado um ataque à biblioteca de interação.
• Não chame MR ou MC antes da chamada a init; isso pode causar comportamento indefinido.
• Você só pode acessar variáveis que definiu e variáveis do tipo info retornadas pela biblioteca. Tentar acessar outras regiões de memória pode causar erros de compilação ou de execução.

Este problema está sujeito, em primeiro lugar, às mesmas restrições de um problema tradicional. Por exemplo, um erro de compilação resulta em 0 ponto no problema inteiro; um erro de execução ou a ultrapassagem dos limites de tempo ou memória resulta em 0 ponto no teste correspondente.

Além dessas condições, se, em um teste, o programa fizer uma chamada de função inválida ou der uma resposta incorreta a uma consulta, receberá 0 ponto nesse teste. Caso contrário, sejam $C_1$ o número de chamadas às funções da biblioteca dentro de init e $C_3$ o maior número de chamadas às funções da biblioteca em qualquer uma das $q$ chamadas de ask. Se $C_1\le3\cdot10^7$ e $C_3$ não exceder o parâmetro de pontuação $M$ desse teste, você receberá os pontos do teste; caso contrário, não os receberá. Observe que, ao calcular $C_1,C_3$, apenas as chamadas a MR e MC são contadas; as chamadas a isempty não são contadas.

Restrições

Para todos os testes, $1\le n\le2\cdot10^5$, $1\le q\le10^6$. Em cada consulta, $1\le u\le n$ e $1\le d\le n-1$.

Propriedade especial A: é garantido que, para todo $i\in[1,n-1]$, o pai do vértice $i+1$ é $i$.

Propriedade especial B: é garantido que todas as consultas satisfazem $u=1$.

Propriedade especial C: é garantido que todas as consultas satisfazem $d\le100$.

Propriedade especial D: é garantido que todas as consultas satisfazem $d\ge1000$.