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:
| #include <bits/stdc++.h> | |
| #define ff first | |
| #define ss second | |
| using namespace std; | |
| const int maxn = 500100; | |
| typedef pair<int, int> ii; | |
| vector<int> v[maxn]; | |
| int dist1[maxn]; | |
| int dist2[maxn]; | |
| ii dfs1(int x, int p) | |
| { | |
| ii ans = {0, x}; | |
| for (int u : v[x]) { | |
| if (u == p) continue; | |
| ans = max(ans, dfs1(u, x)); | |
| } | |
| ans.ff++; | |
| return ans; | |
| } | |
| void dfs2(int *dist, int x, int p) | |
| { | |
| for (int u : v[x]) { | |
| if (u == p) continue; | |
| dist[u] = dist[x]+1; | |
| dfs2(dist, u, x); | |
| } | |
| } | |
| int main() | |
| { | |
| ios_base::sync_with_stdio(false); | |
| cin.tie(0); | |
| int n; | |
| cin >> n; | |
| for (int i = 1; i < n; i++) { | |
| int a, b; | |
| cin >>a >> b; | |
| v[a].push_back(b); | |
| v[b].push_back(a); | |
| } | |
| ii d1 = dfs1(1, 1); | |
| ii d2 = dfs1(d1.ss, d1.ss); | |
| dfs2(dist1, d1.ss, d1.ss); | |
| dfs2(dist2, d2.ss, d2.ss); | |
| for (int i = 1; i <= n; i++) { | |
| int ans = max(dist1[i], dist2[i]); | |
| cout << ans+1 << "\n"; | |
| } | |
| return 0; | |
| } |
