Vamos encontrar o número de sequências ruins: Sequências de tamanho $$k$$ que não passam por nenhuma aresta preta. Então, a resposta será o número total de sequências de tamanho $$k$$ menos a quantidade de sequências ruins.
Ideia Principal: Para contar tais sequências, podemos remover todas as arestas pretas da árvore!
Após removê-las, a árvore se separa em diversas componentes conexas. A resposta de cada componente não depende de outras componentes, já que não podemos escolher um caminho que saia de uma componente e vai para outra, pois ele, necessariamente, passa por uma aresta preta. Para cada uma dessas componentes, devemos contar qual o número de vértices que estão presentes nela. Para isso, basta rodar uma DFS para cada vértice ainda não visitado por ela e incrementar uma variável $$p$$ em $$1$$ para cada novo nó desta componente. Então, se $$p$$ é o número final de vértices de uma componente, a resposta desta componente, ou seja, o número se sequências ruins, é $$p^k$$. Seja $$Sum$$ a soma de todas as respostas de todas as componentes, módulo $$10^9 + 7$$.
Concluindo, a resposta final é $$n^k$$ – $$Sum$$.
https://gist.github.com/Rockbet/01501e957eaff572bad37bd9c12e8daa
Deixe um comentário