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.
| // 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; | |
| } |


Comente