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)$$.