No mundo binário dos computadores, uma árvore de maçãs se parece com uma árvore binária, onde cada galho bifurca-se exatamente em dois novos galhos. Numeramos os pontos da raiz, dos galhos e das pontas das folhas para distinguir diferentes galhos por seus pontos finais. Assumimos que a raiz sempre é numerada como 1 e todos os números usados para numerar estão no intervalo de 1 a N, onde N é o número total de pontos numerados. Por exemplo, na figura abaixo, N é igual a 5.

2 5
/ \\
3 4
\\ /
1

No entanto, não é conveniente colher maçãs de uma árvore quando há muitos galhos. Portanto, alguns deles devem ser removidos. No entanto, queremos minimizar a perda de maçãs. Recebemos a quantidade de maçãs em cada galho e a quantidade de galhos que devem ser preservados. O objetivo é determinar quantas maçãs podem permanecer na árvore após a remoção dos galhos excessivos.

Formato de Entrada

A primeira linha da entrada contém dois números: N e Q (2 ≤ N ≤ 100; 1 ≤ Q ≤ N-1). N denota o número de pontos numerados na árvore. Q denota a quantidade de galhos que devem ser preesrvados. As próximas N-1 linhas contêm descrições dos galhos. Cada descrição consiste em três números inteiros separados por espaços. Os primeiros dois definem o galho pelos seus pontos finais. O terceiro número define o número de maçãs neste galho. Você pode assumir que nenhum galho contém mais de 30000 maçãs.

Formato de Saída

A saída deve conter apenas um número - a quantidade de maçãs que podem ser preservadas. Não se esqueça de preservar a raiz da árvore ;-)

Exemplo de Entrada

5 2
1 3 1
1 4 10
2 3 20
3 5 20

Exemplo de Saída

21
<h3>Solução</h3>
<p>A tarefa consiste em encontrar o subconjunto de Q galhos que maximiza o número de maçãs, mantendo a conexidade com a raiz. Utilizaremos programação dinâmica na árvore para resolver esse problema.</p>
<p>Definimos <code>dp[v][k]</code> como o máximo número de maçãs que podemos obter em uma subárvore com raiz em <code>v</code>, usando exatamente <code>k</code> galhos. A transição será feita considerando todas as possíveis partições dos galhos entre os filhos de um nó.</p>
<p>Código:</p>
<code class="language-cpp">#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
const int MAXQ = 105;

struct Edge {
    int to, weight;
};

vector<Edge> adj[MAXN];
int dp[MAXN][MAXQ];

void dfs(int node, int parent, int q) {
    dp[node][0] = 0;
    for (auto& edge : adj[node]) {
        if (edge.to == parent) continue;
        dfs(edge.to, node, q);
        for (int k = q; k >= 0; --k) {
            for (int j = 0; j <= k; ++j) {
                dp[node][k] = max(dp[node][k], dp[node][k-j] + dp[edge.to][j]);
            }
        }
        dp[node][0] += edge.weight;
    }
}

int main() {
    int N, Q;
    cin >> N >> Q;
    for (int i = 0; i < N - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    dfs(1, -1, Q);
    cout << dp[1][Q] << endl;
    return 0;
}</code>