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: