Solução

Esse é um problema de teoria do grafos.

Primeiro montamos um grafo, com arestas bidirecionais entre todo $$u$$ e $$v$$ que tem ligação de superior/inferior. A partir daí é possível ver que que a solução para um vertice $$v$$ seria a distância máxima entre ele e qualquer outro veŕtice, pois como $$v$$ tem rank 1, então se $$u$$ tem distância $$x$$ de $$v$$, o rank de $$u$$ caso $$v$$ fosse presidente será sua distância, como queremos saber o número de ranks distintos, o vértice de distância máxima apresentará o maior rank, e no seu caminho até $$v$$, haverão todos os outros ranks merores que $$x$$. É possível então fazer uma DFS e computar para cada vértice a distância máxima partindo dele. Porém, essa idéia não passaria no tempo, pois realizamos $$n$$ DFS’s, cada uma com tempo $$O(n)$$, tendo então, $$O(n^2)$$ de tempo para $$n$$ igual a $$5 \cdot 10^5$$, que não passaria no tempo.

É possível porém computar isso se uma forma diferente.

É uma propriedade de uma arvore que para todo vértice, o vértice mais distânte dele fará parte do diâmetro da árvore. Isso significa que para todo vértice de uma árvore, podemos garatir que o mais distante dele será um dos dois vértices do diâmetro daquela árvore.

Podemos então achar o dois vértices do diâmetro da árvore, e computar a distância de cada um deles para todos os outros. A resposta para o vértice $$v$$ será então o $$max(dist_1[v], dist_2[v])$$ sendo dist_1 e dist_2 as distâncias do diâmetros para os vértice $$v$$.

Podemos achar os diâmetros em $$O(n)$$, computar as distâncias partindo deles com duas DFS’s em $$O(n)$$, e para cada $$v$$ achar sua resposta em $$O(1)$$, obtendo então um tempo $$O(n) + O(n) + n*O(1) = O(n)$$.

Código:

https://gist.github.com/fredbr/cd60ecde5e54554540059ae4345ee202