/**
* Solution for CCO 2023 Day 2 Problem 2: Travelling Trader
* * Logic:
* This is a Tree DP problem where we must select a subset of nodes and a traversal order.
* Constraint: Distance between consecutive profit-takes <= K.
* * DP State: dp[u][d_in]
* d_in: The distance from the last selected ancestor.
* Returns: A list of Pareto-optimal results {profit, d_out}.
* d_out: The distance from the last selected node in this subtree to u's parent.
* * Strategies at node u:
* 1. Pick u FIRST: Reset gap to 0 immediately. Then visit children.
* - Good for: Maximizing profit within the subtree (provides gap 1 to children).
* 2. Pick u LAST: Visit children first (passing d_in), then pick u.
* - Good for: Returning a small gap (1) to the parent.
* 3. SKIP u: Visit children passing d_in.
* - Good for: When picking u is impossible or suboptimal (rare).
* * Greedy Chain Logic:
* To merge children results, we use a greedy strategy:
* Always visit the child that allows continuation (valid input gap) and returns the
* SMALLEST output gap. This keeps the "gap budget" loose for subsequent children.
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// --- Constants & Globals ---
const int MAXN = 200005;
struct State {
int d_out;
long long profit;
};
// Result for a child's greedy consideration
struct ChildMove {
int next_req_in; // The input gap this child needs
int ret_out; // The output gap this child returns
long long profit;
int child_idx; // Original index
};
int N, K;
vector<int> adj[MAXN];
vector<int> tree[MAXN];
long long P[MAXN];
// dp[u][d_in] -> List of {d_out, profit}
// d_in ranges 1..K (since d_in=0 is impossible for a child, parent dist >= 1)
// We map 0-based index to 1..K
vector<State> dp[MAXN][4];
// --- Helper Functions ---
void build_tree(int u, int p) {
for (int v : adj[u]) {
if (v != p) {
tree[u].push_back(v);
build_tree(v, u);
}
}
}
// Keep only pareto optimal states: Max profit for each d_out
void optimize_states(vector<State>& states) {
if (states.empty()) return;
// We want to map each d_out (1..K) to max profit.
// Since K is small, just use a fixed array.
long long best_p[5];
fill(best_p, best_p + 5, -1);
for (auto& s : states) {
if (s.d_out <= K+1) { // d_out can be K+1 (invalid/end), but we filter later
// For strict pareto: if we have d_out=1, profit=10,
// and d_out=2, profit=10, the d_out=2 is useless.
// But simpler: just map best profit per d_out.
if (s.profit > best_p[s.d_out]) best_p[s.d_out] = s.profit;
}
}
states.clear();
// Reconstruct pareto frontier
long long max_so_far = -1;
// Iterate from largest gap to smallest.
// If smaller gap doesn't have more profit, it's useless?
// No, smaller gap is structurally better.
// If larger gap has MORE profit, we keep it.
// If smaller gap has LESS profit, we keep it (structural advantage).
for (int d = 1; d <= K + 1; d++) {
if (best_p[d] != -1) {
states.push_back({d, best_p[d]});
}
}
}
// Execute Greedy Chain Strategy
// start_gap: Gap before visiting first child
// force_u_last: If true, we append u at the end
// u_picked_first: If true, we already took profit P[u], start_gap should be 0.
State solve_chain(int u, int start_gap, bool force_u_last, bool u_picked_first) {
long long current_profit = (u_picked_first ? P[u] : 0);
int current_gap = start_gap;
// If we skip u and start_gap >= K, we can't do anything (input to child must be <= K)
// Child input = current_gap + 1. So we need current_gap < K.
if (!u_picked_first && !force_u_last && start_gap >= K) return {start_gap + 1, -1}; // Invalid
// Collect best moves from all children
// Since greedy selection depends on current_gap, and current_gap changes,
// we normally re-evaluate. BUT K is small.
// We can pre-calculate the best move each child offers for input 1, 2, 3...
// Then dynamically pick.
// Store child options: options[v][input_gap] = {ret_gap, profit}
// Optimization: Since we simply want "Smallest Return Gap", we can sort children.
// However, a child might accept input 1 but not 2.
// Let's use a "used" mask.
vector<bool> used(tree[u].size(), false);
while (true) {
int req_in = current_gap + 1;
if (req_in > K) break; // Cannot enter any child
int best_child = -1;
int best_ret = 100;
long long best_gain = -1;
// Scan children
for (int i = 0; i < tree[u].size(); i++) {
if (used[i]) continue;
int v = tree[u][i];
// Look up dp[v][req_in]
// We want the option with Min d_out, then Max profit
for (auto& s : dp[v][req_in]) {
// Return from child is s.d_out.
// New gap at u will be s.d_out + 1.
// We want s.d_out to be small.
if (s.d_out < best_ret) {
best_ret = s.d_out;
best_gain = s.profit;
best_child = i;
} else if (s.d_out == best_ret) {
if (s.profit > best_gain) {
best_gain = s.profit;
best_child = i;
}
}
}
}
if (best_child != -1) {
used[best_child] = true;
current_profit += best_gain;
current_gap = best_ret; // gap at u becomes child's return
// Wait, gap at u becomes child_out + 1?
// DP state stores d_out relative to PARENT.
// s.d_out is distance from Child's profit to Child's Parent (u).
// So s.d_out is exactly the gap at u upon return.
// Correct.
} else {
break;
}
}
if (force_u_last) {
// We try to append u
// Valid if current_gap + 1 <= K?
// No, "gap" is distance from last profit.
// We are at u. Distance is current_gap.
// If we pick u, distance becomes 0.
// Condition: current_gap <= K. (Actually distance from last profit).
// Since we enforced req_in <= K for children steps, current_gap is always valid dist?
// Yes, current_gap is exactly dist to last profit.
if (current_gap <= K) {
current_profit += P[u];
current_gap = 0;
} else {
return {100, -1}; // Fail
}
}
// Final d_out relative to u's parent is current_gap + 1
return {current_gap + 1, current_profit};
}
void solve(int u) {
// Post-order DFS
for (int v : tree[u]) solve(v);
// Calculate for all incoming gaps
for (int d_in = 1; d_in <= K; d_in++) {
// Strategy 1: Pick First
// Start gap 0.
State s1 = solve_chain(u, 0, false, true);
if (s1.profit != -1) dp[u][d_in].push_back(s1);
// Strategy 2: Pick Last
// Start gap d_in.
State s2 = solve_chain(u, d_in, true, false);
if (s2.profit != -1) dp[u][d_in].push_back(s2);
// Strategy 3: Skip
// Start gap d_in.
State s3 = solve_chain(u, d_in, false, false);
if (s3.profit != -1) dp[u][d_in].push_back(s3);
optimize_states(dp[u][d_in]);
}
}
// Global Path Reconstruction
vector<int> final_path;
void reconstruct(int u, int start_gap, int strategy) {
// 1: Pick First, 2: Pick Last, 3: Skip
bool u_picked_first = (strategy == 1);
bool force_u_last = (strategy == 2);
if (u_picked_first) final_path.push_back(u);
int current_gap = (u_picked_first ? 0 : start_gap);
vector<bool> used(tree[u].size(), false);
// Re-run greedy loop to find child order
while (true) {
int req_in = current_gap + 1;
if (req_in > K) break;
int best_child = -1;
int best_ret = 100;
long long best_gain = -1;
// Need to identify WHICH state of child was used?
// We assumed we picked the optimal one.
// We need to match the specific outcome.
// To simplify: Just look for the move that is "optimal" locally.
// This works because the DP value was built using this exact greedy logic.
for (int i = 0; i < tree[u].size(); i++) {
if (used[i]) continue;
int v = tree[u][i];
for (auto& s : dp[v][req_in]) {
if (s.d_out < best_ret) {
best_ret = s.d_out;
best_gain = s.profit;
best_child = i;
} else if (s.d_out == best_ret) {
if (s.profit > best_gain) {
best_gain = s.profit;
best_child = i;
}
}
}
}
if (best_child != -1) {
used[best_child] = true;
// Recurse into child
int v = tree[u][best_child];
// Determine Child Strategy
// We know child received req_in and produced best_gain/best_ret.
// We check which strategy at child yields this.
// Order preference: Pick First, Pick Last, Skip.
// (Must match DP build order or logic).
int child_strat = 0;
// Check Strat 1
bool found = false;
// We need to re-call solve_chain or just peek DP?
// DP stores merged results. We need to check hypothetical.
// Since we don't store strategy source in DP, we check by re-solving.
// Check Pick First (1)
State c1 = solve_chain(v, 0, false, true);
if (c1.d_out == best_ret + 1 && c1.profit == best_gain) child_strat = 1;
else {
// Check Pick Last (2)
State c2 = solve_chain(v, req_in, true, false);
if (c2.d_out == best_ret + 1 && c2.profit == best_gain) child_strat = 2;
else child_strat = 3; // Skip
}
reconstruct(v, req_in, child_strat);
current_gap = best_ret;
} else {
break;
}
}
if (force_u_last) final_path.push_back(u);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if (!(cin >> N >> K)) return 0;
for (int i = 0; i < N - 1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 1; i <= N; i++) cin >> P[i];
build_tree(1, 0);
solve(1);
// Root (1) must be picked.
// It is equivalent to "Pick First" with dummy input.
// Or just check which strategy at root yields max profit.
// Since root is picked, only Strat 1 or 2 possible.
long long ans = -1;
int best_strat = 1;
// Check Strat 1 (Pick First)
State s1 = solve_chain(1, 0, false, true);
if (s1.profit > ans) { ans = s1.profit; best_strat = 1; }
// Check Strat 2 (Pick Last) -- Only valid if input valid?
// Root input is conceptually 0? No, root has no parent.
// But "Pick Last" implies we traverse children BEFORE root.
// Children would need input gap.
// If we assume trader starts at 1, he is AT 1.
// He can take profit immediately (Pick First).
// Can he delay 1? "Trader starts by doing business in city 1".
// Problem says: "starts by doing business in city 1".
// So Strategy 1 (Pick First) is MANDATORY for root.
ans = s1.profit;
best_strat = 1;
cout << ans << endl;
reconstruct(1, 0, best_strat);
cout << final_path.size() << endl;
for (int i = 0; i < final_path.size(); i++) {
cout << final_path[i] << (i == final_path.size() - 1 ? "" : " ");
}
cout << endl;
return 0;
}
