Solução por Rogério Júnior
O mapa das salas pode ser observado como um grafo. Mais que isso, sabemos, pelo número de arestas, que o grafo é uma árvore. Observe o exemplo de árvore abaixo:
Suponha que o jogador começa da sala 1. A sala mais distante do começo é a sala 5, e para chegar nela, precisamos atravessar 3 corredores. Deste modo, se o número de corredores pelos quais podemos passar for no máximo 3, podemos passar por quatro salas (1, 3, 4, 5), descobrindo uma nova a cada corredor que visitamos. Porém, se o valor de M for 4, por exemplo, não conseguirei visitar nenhuma nova sala. Se M for 5, posso visitar, por exemplo, a sala 2, voltar para a sala 1 e depois fazermos o passeio que tínhamos feito anteriormente. O que ocorre é que, dado um caminho principal (caminho por onde não passo pela mesma aresta duas vezes) podemos descobrir n de seus vértices explorando exatamente n corredores. Se, entretanto, decidimos sair do caminho principal, descobriremos n salas passando por n corredores e depois teremos que passar pelos mesmos n corredores para voltarmos ao caminho principal, por onde saímos.
Deste modo, se temos a salas no caminho principal e b salas em caminhos secundários, passaremos por exatamente a+2b corredores para visitá-las. Deste modo, é sempre vantajoso ter o maior número possível de salas no caminho principal, para reduzirmos a quantidade de corredores. Para isso, o caminho principal deve ser exatamente o caminho entre o vértice de origem e o vértice mais distante dele.
Uma vez que sabemos que o comprimento deste caminho é o inteiro maior e podemos passar por m corredores, podemos descobri exatamente 1 (sala inicial) + maior (salas no caminho principal) + (m-maior)/2 (salas em caminhos secundários). Observe que precisamos de cuidados para que o resultado não seja negativo, visto que nem sempre m é maior que maior.
O problema agora resume-se a, para cada vértice, sabermos o valor de maior. Como o gafo é uma árvore, sabemos que o vértice mais distante será uma das pontas do diâmetro. Sejam d1 e d2 duas pontas de um diâmetro. Para encontrá-los, usaremos o mesmo algoritmo mostrado no Problema Avançado da Semana 9. Faremos uma DFS no vértice 1 e o vértice mais distante será d1. Depois faremos uma DFS em d1 e o vértice mais distante será d2, lembrando de guardar todas as distâncias de um vértice v a d1 em dist[1][v].Por último, faremos uma DFS em d2 e guardaremos todas as distâncias de um vértice v a d2 em dist[2][v]. Chamaremos essas DFS's de dfs1, dfs2 e dfs3, respectivamente. Para cada query (A, M), o valor de maior será a distância para o mais distante entre d1 e d2 (maior = max(sit[1][A], dist[2][Ad), e para encontrarmos a maior quantidade de salas exploráveis, usando a conta feita anteriormente mas com o cuidado para não a negativarmos ou imprimirmos uma quantidade de salas maior que n, basta imprimirmos o resultado da expressão: min(n, min(m+1, maior+1) + max(0, (m-maior)/2)). Segue o código para melhor entendimento.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // São João - Seletiva IOI 2014 | |
| // Rogério Júnior | |
| // Complexidade: O(v) | |
| #include <vector> // vector | |
| #include <cstdio> // scanf e printf | |
| using namespace std; // para uso do C++ | |
| #define PB push_back // por comodidade | |
| #define MAXN 100100 // defino o valor de MAXN | |
| // declaro as variáveis que vou usar | |
| int n, v, d1, d2, dist[3][MAXN]; | |
| // salvarei o grafo em uma lista de adjacências | |
| vector<int> lista[MAXN]; | |
| // primeira DFS | |
| void dfs1(int u){ | |
| // para cada vizinho p de u | |
| for(int i=0; i<lista[u].size(); i++){ | |
| int p=lista[u][i]; | |
| // se o já tiver visitado (ele for pai de u) | |
| // vou para a próxima iteração do for | |
| if(dist[0][p]>0) continue; | |
| // a distância da origem a p | |
| // é a distância da origem a u, somada de 1 | |
| dist[0][p]=dist[0][u]+1; | |
| // lembro de guardar o vértice mais distante da origem | |
| if(dist[0][p]>dist[0][d1]) d1=p; | |
| // e chamo a DFS em p | |
| dfs1(p); | |
| } | |
| } | |
| // segunda DFS | |
| void dfs2(int u){ | |
| for(int i=0; i<lista[u].size(); i++){ | |
| int p=lista[u][i]; | |
| if(dist[1][p]>0) continue; | |
| dist[1][p]=dist[1][u]+1; | |
| if(dist[1][p]>dist[1][d2]) d2=p; | |
| dfs2(p); | |
| } | |
| } | |
| // terceira DFS | |
| void dfs3(int u){ | |
| for(int i=0; i<lista[u].size(); i++){ | |
| int p=lista[u][i]; | |
| if(dist[2][p]>0) continue; | |
| dist[2][p]=dist[2][u]+1; | |
| dfs3(p); | |
| } | |
| } | |
| int main(){ | |
| // leio o valor de n | |
| scanf("%d", &n); | |
| // para cada aresta | |
| for(int i=1; i<n; i++){ | |
| // leio os vértices que a ligam | |
| int p, q; | |
| scanf("%d %d", &p, &q); | |
| // e adiciono a aresta na lista de adjacências | |
| lista[p].PB(q); | |
| lista[q].PB(p); | |
| } | |
| // o vértice 1 será a origem da primeira DFS | |
| // logo dist[0][1] será zero | |
| dist[0][1]=0; | |
| // chamo a DFS em 1 | |
| dfs1(1); | |
| // faço a DFS na primeira ponta do diâmetro | |
| dist[1][d1]=0; | |
| dfs2(d1); | |
| // e depois na segunda ponta | |
| dist[2][d2]=0; | |
| dfs3(d2); | |
| // agora tenho as distância de quaisquer vértices | |
| // a qualquer uma das pontas do diâmetro | |
| // leio a quantidade de queries | |
| scanf("%d", &v); | |
| // para cada query | |
| for(int i=1; i<=v; i++){ | |
| // leio os valores de a e m | |
| int a, m; | |
| scanf("%d %d", &a, &m); | |
| // vejo qual ponta do diâmetro está mais distante de a | |
| int maior=max(dist[1][a],dist[2][a]); | |
| // e imprimo a resposta | |
| printf("%d\n", min(n, min(m+1, maior+1) + max(0, (m-maior)/2))); | |
| } | |
| return 0; | |
| } |