#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;
vector<int> values;
vector<bool> visited;
int N, K;
void printPath(const vector<int>& path) {
cout << "Path: ";
for(int node : path) {
cout << node << " ";
}
int weight = 0;
for(int node : path) {
weight += values[node-1];
}
cout << "Weight: " << weight << endl;
}
int findMaxPathWeight(int node, int pathLength, vector<int>& currentPath) {
// Base case: if we have a path of length K
if (pathLength == K) {
printPath(currentPath);
int totalWeight = 0;
for(int n : currentPath) {
totalWeight += values[n-1];
}
return totalWeight;
}
visited[node] = true;
int maxWeight = 0;
// Try each neighbor
for(int next : adj[node]) {
if(!visited[next]) {
currentPath.push_back(next);
int weight = findMaxPathWeight(next, pathLength + 1, currentPath);
maxWeight = max(maxWeight, weight);
currentPath.pop_back();
}
}
visited[node] = false;
return maxWeight;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> K;
adj.resize(N + 1);
values.resize(N);
visited.resize(N + 1, false);
cout << "Reading " << N << " values:" << endl;
for(int i = 0; i < N; i++) {
cin >> values[i];
cout << "Value[" << (i+1) << "] = " << values[i] << endl;
}
cout << "Reading " << (N-1) << " edges:" << endl;
for(int i = 0; i < N - 1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
cout << "Edge: " << u << " - " << v << endl;
}
vector<int> currentPath = {1};
int result = findMaxPathWeight(1, 1, currentPath);
cout << "Final result: " << result << endl;
return 0;
}