Solução Informática - Nível Avançado - Semana 41

Escrito por Caique Paiva

Conhecimentos Prévios Necessários:

DP em Árvore
Decomposição em Raiz

Esse problema tem muitas soluções. A mais rápida que eu conheço é em $O(nlog)$ , mas ela é bem complicada. Vou apresentar uma mais simples, que é em $O(n\sqrt{n} log n)$ , e como o tl do problema é de 7 segundos, com uma implementação boa, ela passa.

Como resolver com $k$ fixo?

Vamos calcular isso com uma dp! Seja $dp(v) =$ um par de números: { A quantidade de caminhos de tamanho $k$ na subárvore de $v$ , O tamanho do maior caminho que começa por $v$ e passa somente por vértices que não foram escolhidos em um caminho ainda }. Feito isso, como vai ser a transição?

Seja $x$ um filho de $v$ . Temos que

$dp(v).first += dp(x).first$

Pois todo caminho de tamanho $k$ escolhido na subárvore de $x$ também pertence a subárvore de $v$ .

Agora, para $dp(v).second$ , temos duas possibilidades.

Seja $x_1, x_2$ dois filhos tal que $dp(x_1).second$ é máximo e $dp(x_2).second$ é o segundo maior. Temos que, caso $dp(x_1).second + dp(x_2).second + 1 \ge k$ , então, faça $dp(v).first++$ , pois caso isso seja verdade, podemos criar outro caminho de tamanho $k$ , e então, faça $dp(v).second = 0$ .
Caso isso não aconteça, faça $dp(v).second = dp(x_1).second + 1$ , pois esse é o maior caminho que podemos criar.

No final, basta retornar $dp(1).first$ , e isso vai ser nossa resposta!

Conseguimos resolver o $k$ fixo em $O(N)$ !! Só temos um problema, se rodarmos esse código para cada $k$ , temos um código $O(N^2)$ , que não passa :(, como podemos otimizar? Seja $f(k)$ a resposta para um certo $k$ .

Lema: $f(k) \le \frac{n}{k}$

Isso é verdade pois cada vértice pertence a no máximo 1 caminho e cada caminho tem $k$ vértices, então, se tivermos mais que $\frac{n}{k}$ caminhos, vamos ter que ter usado mais que $\frac{n}{k} k = n$ vértices, o que é um absurdo. Esse lema acaba o problema! Pois isso implica que vamos ter no máximo $O(\sqrt{n})$ valores distintos de $f(k)$ ! Pois, caso $k \ge \sqrt{n}$ , então $\frac{n}{k} \le \sqrt{n}$ , ou seja, de $[\sqrt{n}, n]$ , temos no máximo $\sqrt{n}$ valores, e entre $[1, \sqrt{n}]$ , obviamente temos $\sqrt{n}$ valores no máximo. Agora, veja que $f(k) \le f(k+1)$ , portanto, a ideia vai ser o seguinte algoritmo, começando com $x = 1$ :

Primeiro, calculamos $f(x)$ , e agora, vamos fazer uma busca binaria para achar o último $y$ tal que $f(x) = f(y)$ , então, vamos ter que $f(x) = f(x+1) = \cdots = f(y)$ . Então, em $O(Nlog)$ , conseguimos achar esse $y$ , e fazemos $x = y+1$ .

Agora, como temos no máximo $O(\sqrt{n})$ valores diferentes, esse algoritmo só vai ser aplicado $\sqrt{n}$ vezes, então, a complexidade no final fica $O(n\sqrt{n}log)$ .

Clique aqui para ver o código