<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

547. Divide The Kingdom
Time limit per test: 1 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Once upon a time, long, long ago there lived a King and a Queen who ruled over a distant kingdom called Berland.

Their kingdom contained n cities connected by n-1 bi-directional roads. The roads were constructed in such a way that Berland citizens were able to reach any city from any other city by walking along these roads.

One day the King and the Queen decided that they want to break up the relationship. Yes, it's not common when it comes to a royal marriage, but it's something they decided to do and we have to respect their decision. Of course, now they want to divide the kingdom and start living separately from each other. Each of them wants to take a part of the existing kingdom. Moreover, they want their own parts to be very special, so their requirements are quite complicated.

So, the King wants to pick a nonempty subset of cities from the existing kingdom. He will be satisfied only if all following conditions are met:
his subset of cities is connected (i.e. for every pair of his cities A and B, there is always a path from A to B that passes only through the King's cities),
he does not share any cities with the Queen,
none of his cities are directly connected by a road to any of the Queen's cities,
if you consider distances between all pairs of his cities, the length of the longest path must be equal to D1,
if you consider all pairs of his cities which are located at distance D1 from each other and then calculate the number of different cities within all these pairs, this number must not exceed C1 (formally, if his subset contains the only city then the number of such pairs equals 0).


The Queen wants to pick a nonempty subset of cities as well. Her requirements are essentially the same as the King's ones, with the exception of the numbers she has in mind — D2 and C2 respectively. Obviously, she is not allowed to take cities which have been already taken by the King, her subset of cities should be connected and none of her cities should be adjacent to the King's cities.

Now, what about the remaining cities, the ones that will not belong to either the King or the Queen after the kingdom is divided? The answer is simple — they have to be destroyed along with all roads coming into them, and all people should be evacuated from these cities. Destroying the i-th city will cost pi burles.

Can you help the King and the Queen with the separation? You task is to figure out whether it's possible to perform separation of the kingdom according to the rules described above. If the separation is possible, you have to find a way with the minimum possible cost of cities that will be destroyed.

Input
The first line of the input contains a positive integer n (3 ≤ n ≤ 200) — the number of cities in the kingdom. The second line contains integers D1, C1, D2, C2 (0 ≤ D1, D2 ≤ n-1, 1 ≤ C1, C2 ≤ n). The third line contains n integer costs pi (1 ≤ pi ≤ 1000). Each of the next n-1 lines contains two integer numbers aj and bj (1 ≤ aj, bj ≤ n), meaning that the j-th road connects cities aj and bj.

Output
If there is no solution, write "-1" (without the quotes) in a single output line.

Otherwise, output the total cost of destroyed cities in the first line, and print the numbers of destroyed cities in the increasing order in the second line. If there are multiple solutions, you may print any of them.

Example(s)
sample input
sample output
10
4 2 0 1
5 2 5 2 5 5 5 5 5 2
1 4
6 1
1 2
7 1
3 7
10 7
9 10
7 8
8 5
6
2 4 10

sample input
sample output
4
1 2 1 2
9 9 9 9
1 2
2 3
3 4
-1



Note
In the first test case, the optimal solution is as follows:




In the first place, city 10 is destroyed and the kingdom falls apart into two parts. The smallest part contains an isolated city 9, and it already satisfies the Queen's requirements.
The second remaining part is a little bit too large for the King. The maximum distance between pairs of cities (2,5), (4,5), (6,5) is 4, exactly as the King wants. But the number of these cities [2, 4, 5, 6] is 4, while the King's desire is to have not more than 2. So, it's additionally required to destroy cities 2 and 4.
Overall, destroying cities [2, 4, 10] costs 6 burles. It's an optimal solution from the cost perspective.


In the second test case there is no solution. Obviously, at least one city should be deleted from the kingdom, while D1=1 requires two adjacent cities, and D2=1 requires another two adjacent cities. So, we could possibly achieve the required outcome with 5 cities in a line, but not with 4.

<|response|>
1. Abridged problem statement
-----------------------------

We are given a tree with `n` vertices (`3 ≤ n ≤ 200`). Deleting vertex `i` costs `p[i]`.

We must choose:

- a nonempty connected set of vertices for the King (a subtree),
- a nonempty connected set of vertices for the Queen (another subtree),

such that:

- The two sets are disjoint.
- No edge connects a King vertex directly to a Queen vertex (distance between sets ≥ 2).
- For King’s subtree:
  - Its diameter (maximum distance between any two vertices in it) is exactly `D1`.
  - Among all pairs of vertices at distance `D1` within this subtree, count the number of **distinct endpoints** that appear in such pairs; this count ≤ `C1`.
- For Queen’s subtree: same constraints with `D2`, `C2`.

All other vertices are destroyed (paying their costs). We want to minimize the total destruction cost. If impossible, print `-1`; else print the minimal cost and the list of destroyed vertices.


2. Key observations
-------------------

1. **Distance ≥ 2 between King and Queen ⇒ there is a cut vertex between them.**

   If we take the (unique) path between any King vertex and any Queen vertex, its length is ≥ 2. This path contains some middle vertex (or vertices) that are not in either King or Queen. In particular, there exists at least one vertex whose removal disconnects King and Queen’s subtrees into different components of the remaining tree.

   We can explicitly choose such a vertex `split` and say: nobody takes `split`. King’s and Queen’s subtrees must lie in *different* connected components of the tree with `split` removed.

2. **Once `split` is fixed, King and Queen are completely independent in different components.**

   If:

   - we remove `split`,
   - partition the remaining graph into connected components `C1, C2, ..., Cm`,

   then any valid solution with this fixed `split` must place:

   - the King’s subtree inside one component `Ci`,
   - the Queen’s subtree inside another different component `Cj`.

   Inside one component, we just need a single tree (no adjacency constraints with the other person, since they live in a different component and neither uses `split`).

3. **Transform the problem to: best constrained subtree in a given tree.**

   For a fixed component (a tree `T` with node set `nodes`) and given parameters `(D, C)`:

   > Find a connected nonempty subset `S ⊆ nodes` maximizing `sum(p[v] for v in S)` such that:
   > - `diameter(S) = D`
   > - the number of distinct vertices that appear as endpoints of diameter-`D` pairs is ≤ `C`.

   This is the core subproblem we must solve for:
   - `(D1, C1)` for the King,
   - `(D2, C2)` for the Queen,
   in each component.

4. **Structure of diameter‑constrained subtrees.**

   In any tree:

   - If diameter `D` is **even**, then any tree with diameter `D` has a **central vertex**, at equal distance `D/2` from all diameter endpoints.
   - If diameter `D` is **odd**, then any such tree has a **central edge (u,v)**; each endpoint of the diameter is at distance `(D-1)/2` from either `u` or `v`, on opposite sides.

   Given a candidate center (vertex or edge), we can characterize the optimal subtree:

   - Let `R = floor(D/2)`.
   - All nodes at distance `< R` from the center are “interior”; they can be included freely (they don’t increase the diameter beyond `D`).
   - Nodes at distance exactly `R` are “boundary”; their selection determines the diameter endpoints and must satisfy:
     - We must have diameter exactly `D` ⇒ need endpoints in *at least two different directions* from the center (two different child-subtrees of the center, or both sides of the central edge).
     - The total number of distinct endpoints (picked boundary nodes) must be ≤ `C`.
   - Costs are positive ⇒ we always want to include all interior nodes, and we pick boundary nodes by highest value, under the above structural constraints.

5. **All-pairs shortest paths help to make each try fast.**

   `n ≤ 200`, so we can precompute:

   - `dist_all[s][v]` = distance from `s` to `v` (via BFS from each `s`, `O(n^2)` total),
   - `first_step[s][v]` = neighbor of `s` on a shortest path from `s` to `v`.

   These allow:

   - For each candidate center vertex `root`, to classify nodes by distance from `root` quickly.
   - For each boundary node at distance `R` from `root`, to know *through which child* of `root` it is reached (`first_step[root][v]`), thereby grouping boundary nodes by child-subtree.
   - For each candidate center edge `(u,v)`, to assign each node to the closer side and compute its distance to that side.

6. **Complexity.**

   - Precomputation: `O(n^2)` BFS.
   - For each `split` (`n` choices):
     - Build components in `O(n)`.
     - For a component of size `k`, solving best subtree for one `(D,C)` is `O(k^2)`:
       - Even D: try each center vertex (`k` roots), scan all `k` nodes per root.
       - Odd D: try each edge (`≈k` edges), scan all `k` nodes per edge.
     - For both King & Queen, still `O(k^2)`, and `∑k = n`.
     - So per split: `O(n^2)`. Over all splits: `O(n^3)`, which is fine for `n ≤ 200`.

   Memory is also fine: `dist_all` and `first_step` are `200×200` arrays.

7. **Special case `D=0`.**

   A tree with diameter 0 must have exactly one node.

   - If `D = 0` and `C ≥ 1`, any single node subtree with cost `p[v]` satisfies the constraints (0 endpoints at max distance 0, thus ≤ C). For a given component, we just pick the node with maximum `p[v]`.
   - If `D = 0` and `C = 1`, this is exactly the same; code treats it specially.
   - Attempts with `D>0` and `C=1` are impossible: a positive diameter requires at least two distinct endpoints.


3. Full solution approach
-------------------------

We now combine the ideas into a concrete algorithm.

### 3.1 Overall structure

1. Read the input tree `adj`, values `p[i]`, parameters `(D1, C1)` and `(D2, C2)`.

2. Precompute:
   - `dist_all[s][v]` using BFS from each `s`.
   - `first_step[s][v]` while doing BFS.

3. Let `total_sum = sum(p)`.

4. For each `split` in `0..n-1`:

   1. Remove `split` from the graph (logically):
      - Perform DFS/BFS from each neighbor of `split`, not crossing `split`, to extract connected components `comp_0, comp_1, ..., comp_{m-1}`.

   2. For each component `comp_i`:

      - Compute `(best1_sum[i], best1_nodes[i])` = best King-subtree inside `comp_i` obeying `(D1,C1)`.
      - Compute `(best2_sum[i], best2_nodes[i])` = best Queen-subtree inside `comp_i` obeying `(D2,C2)`.

   3. For every pair of distinct components `i < j`:

      - Case A: King in `comp_i` (using `best1[i]`), Queen in `comp_j` (using `best2[j]`).
        - If both sums are valid (not `-∞`), total kept sum = `best1_sum[i] + best2_sum[j]`.
      - Case B: King in `comp_j` (`best1[j]`), Queen in `comp_i` (`best2[i]`).
        - Similarly compute kept sum.

      Track the global maximum kept sum `best` and remember the union of the chosen node sets (`best_selected_global` = all nodes assigned to either King or Queen).

5. After all splits, if `best < 0` (i.e. never found a valid King & Queen combination), print `-1`.

6. Else:

   - Mark all nodes in `best_selected_global` as “kept”.
   - All others (including the selected `split` for that best solution, plus any unused nodes in its components, and any other components) are destroyed.

   - Destruction cost is `total_sum - best`. Or equivalently, sum of `p[i]` for all nodes not kept.

   - Output the cost and the sorted list of destroyed vertices (1-based indices).

### 3.2 Solving “best subtree in a component” for fixed `(D,C)`

Given a set `nodes` describing one component, we solve for `(D,C)`:

```text
best_subtree_in_component(nodes, D, C) -> (max_sum, chosen_nodes)
```

#### Special case: `D = 0`

- If `D = 0 and C = 1`:
  - The subtree must be a single vertex; pick `v in nodes` maximizing `p[v]`.

- For other combinations with `D = 0, C ≥ 1`, the general logic (below) also handles them in our implementation by directly using the `D=0` branch in the per-root function.

#### Case 1: `D` is even (`D = 2R`)

We interpret the subtree as having a central vertex `root`.

For each `root in nodes`:

1. `target = R = D/2`.

2. Start sum: `ssum = p[root]`, `selected = {root}`.

3. For each `v in nodes, v != root`:

   - `dv = dist_all[root][v]`.

   - If `dv < target`:
     - interior node, include: `ssum += p[v]`, `selected.push_back(v)`.

   - Else if `dv == target`:
     - boundary node, collect into a `boundary` list.

4. If `boundary.size() < 2`:
   - Can’t achieve diameter `D` with root as center; skip this root.

5. We need diameter endpoints from at least two different child-subtrees of `root`.

   - For each boundary node `v`:
     - Let `cid = first_step[root][v]` (the neighbor of `root` on shortest path `root->v`).
     - For each child `cid`, keep the best value boundary node: store `best_val[cid]` and `best_node[cid]`.

   - If the number of distinct child IDs with a candidate < 2, skip this root.

6. Pick mandatory endpoints:

   - Among all `cid`, pick `first_v` = boundary node with maximum `p[v]` (some child `first_cid`).
   - Among all other children (`cid != first_cid`), pick `second_v` = boundary node with maximum `p[v]`.

   - Include both: `ssum += p[first_v] + p[second_v]`, add to `selected`.

7. Extra endpoints if allowed:

   - Currently, for `D > 0`, we always have at least 2 endpoints.
   - If `C > 2`, we can add more boundary nodes, staying under the limit C of distinct endpoints.

   - Let `rem = {boundary nodes} \ {first_v, second_v}`.
   - We can choose up to `to_take = min(len(rem), C - 2)` of them with maximum `p[v]`.
     - In C++ we can use `nth_element`; in Python we just sort this small list by `p[v]` descending.

   - Add these to `ssum` and `selected`.

8. Keep the best `(ssum, selected)` over all roots. If none are valid, return `(-∞, empty)`.

#### Case 2: `D` is odd (`D = 2R+1`)

Now the center is an edge `(u, v)`.

We only consider edges completely inside the component:

- For each `u in nodes`:
  - For each neighbor `v in adj[u]` such that `u < v` and `v in nodes`:
    - treat `(u, v)` as central edge.

For each such edge:

1. If `D == 0 or C == 1`, impossible in this odd length case (handled up-front in code).

2. `target = R = (D - 1) // 2`.

3. Start with `u` and `v` included:

   - `ssum = p[u] + p[v]`, `selected = [u, v]`.

4. If `target == 0` (i.e. `D = 1`):

   - The subtree of diameter 1 is simply `{u,v}` (one edge). With `C >= 2`, this is valid; return these.

5. For every other node `w in nodes`:

   - `du = dist_all[u][w]`, `dv = dist_all[v][w]`.

   - If `du < dv` (w is closer to u-side):
     - If `du < target`: interior on u-side ⇒ include it.
     - If `du == target`: boundary candidate on u-side ⇒ add to `bound_u`.

   - Else (dv ≤ du, closer to v-side):
     - If `dv < target`: interior on v-side ⇒ include.
     - If `dv == target`: boundary candidate on v-side ⇒ add to `bound_v`.

6. We must form diameter endpoints from both sides:

   - If `bound_u` or `bound_v` is empty, we can’t get endpoints at distance `D` from each other ⇒ skip this edge.

7. Select endpoints:

   - `bu` = node in `bound_u` with maximum `p`.
   - `bv` = node in `bound_v` with maximum `p`.

   - Add them: `ssum += p[bu] + p[bv]`, include them in `selected`.

8. Extra endpoints if allowed (`C > 2`):

   - `rem = (bound_u \ {bu}) ∪ (bound_v \ {bv})`
   - Choose up to `to_take = min(len(rem), C - 2)` highest-value vertices, include them.

9. Track maximal `(ssum, selected)` over all edges.

Return the best or `(-∞, empty)` if all edges fail.

That concludes `best_subtree_in_component`.

### 3.3 Correctness sketch

- Fix some optimal solution (King-subtree S₁, Queen-subtree S₂). They satisfy all adjacency constraints, so every path from a King vertex to a Queen vertex has length ≥ 2. Pick a vertex `split` on some shortest King–Queen path that is *not* part of either S₁ or S₂ (or an endpoint if needed). Removing `split` splits the tree; S₁ and S₂ are contained in two distinct components. Thus, there exists a `split` for which the algorithm considers exactly the partition containing the optimal solution—so `best` is at least as good as the optimum.

- For a fixed component and parameters `(D,C)`, our construction, given a center (vertex or edge), includes:
  - all interior nodes (helpful, never increase diameter),
  - a carefully chosen set of boundary nodes:
    - enough to realize diameter exactly `D` (two endpoints in different directions),
    - not more than `C` endpoints (count of distinct boundary vertices used),
    - greedily by `p` value among all valid options.
  
  Thus for each fixed center, we get an optimal subtree under that center structure. We also enumerate all possible centers (roots or edges), so among them we get a globally optimal subtree in that component.

- Since costs `p` are positive, adding interior nodes always improves the sum and never invalidates constraints, so greedily including all of them is optimal.

- The outer loops try all splits and all assignments (King’s subtree in one component, Queen’s in another). Among all these, the best valid combination must be found.

So the algorithm is correct and runs in `O(n^3)` as argued.


4. C++ implementation with detailed comments
--------------------------------------------

```cpp
#include <bits/stdc++.h>
using namespace std;

const long long NEG_INF = (long long)-4e18;

int n;
int d1, c1, d2, c2;
vector<int> p;
vector<vector<int>> adj;

// dist_all[s][v] = distance from s to v
// first_step[s][v] = neighbor of s that is the first hop on shortest path from s to v
vector<vector<int>> dist_all;
vector<vector<int>> first_step;

// ---------- Read input ----------
void read_input() {
    cin >> n >> d1 >> c1 >> d2 >> c2;
    p.resize(n);
    for (int i = 0; i < n; ++i) cin >> p[i];
    adj.assign(n, {});
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
}

// ---------- Precompute all-pairs shortest distances and first steps ----------
void precompute_all_pairs() {
    const int INF = 1e9;
    dist_all.assign(n, vector<int>(n, INF));
    first_step.assign(n, vector<int>(n, -1));

    queue<int> q;
    for (int s = 0; s < n; ++s) {
        // BFS from source s
        dist_all[s][s] = 0;
        while (!q.empty()) q.pop();
        // Initialize direct neighbors
        for (int u : adj[s]) {
            dist_all[s][u] = 1;
            first_step[s][u] = u;
            q.push(u);
        }
        // BFS expansion
        while (!q.empty()) {
            int v = q.front(); q.pop();
            int dv = dist_all[s][v];
            for (int u : adj[v]) {
                if (dist_all[s][u] == INF) {
                    dist_all[s][u] = dv + 1;
                    first_step[s][u] = first_step[s][v];
                    q.push(u);
                }
            }
        }
    }
}

// ---------- Best subtree for even D, centered at root (fast, using distances) ----------
pair<long long, vector<int>> best_subtree_from_root_fast(
    int root, const vector<int>& nodes, int D, int C
) {
    // If D = 0, the subtree must be a single vertex
    if (D == 0) {
        if (C >= 1) {
            return { (long long)p[root], vector<int>{root} };
        } else {
            return { NEG_INF, {} };
        }
    }
    // If diameter > 0, we need at least two endpoints ⇒ C must be ≥ 2
    if (C == 1) {
        return { NEG_INF, {} };
    }

    int target = D / 2;  // distance from root to diameter endpoints
    long long sum = p[root];
    vector<int> selected;
    selected.push_back(root);
    vector<int> boundary;      // nodes at distance exactly target
    boundary.reserve(nodes.size());

    // Classify nodes by distance from root
    for (int v : nodes) {
        if (v == root) continue;
        int dv = dist_all[root][v];
        if (dv < target) {
            // strictly inside => always include
            sum += p[v];
            selected.push_back(v);
        } else if (dv == target) {
            // boundary => candidate endpoint
            boundary.push_back(v);
        }
        // nodes with dv > target are not allowed, they would extend diameter
    }

    if ((int)boundary.size() < 2) {
        // cannot form required diameter with root as center
        return { NEG_INF, {} };
    }

    // We need endpoints in at least two distinct child-subtrees of root
    // best_val[cid] = best p[v] among boundary nodes that go through child cid
    // best_node[cid] = corresponding vertex
    static vector<int> best_val;
    static vector<int> best_node;
    if ((int)best_val.size() < n) {
        best_val.assign(n, INT_MIN);
        best_node.assign(n, -1);
    }

    vector<int> touched;   // which child ids have at least one candidate

    for (int v : boundary) {
        int cid = first_step[root][v];  // child of root on path root->v
        if (cid < 0) continue;          // should not happen in a connected component
        if (p[v] > best_val[cid]) {
            if (best_node[cid] == -1) {
                touched.push_back(cid); // first time we use this child
            }
            best_val[cid] = p[v];
            best_node[cid] = v;
        }
    }

    if ((int)touched.size() < 2) {
        // only one subtree gives boundary nodes => cannot have endpoints in 2 directions
        for (int cid : touched) {
            best_val[cid] = INT_MIN;
            best_node[cid] = -1;
        }
        return { NEG_INF, {} };
    }

    // Choose overall best boundary node (first_v) and which child it belongs to
    int first_cid = -1;
    int first_v = -1;
    int max_val = INT_MIN;

    for (int cid : touched) {
        if (best_val[cid] > max_val) {
            max_val = best_val[cid];
            first_cid = cid;
            first_v = best_node[cid];
        }
    }

    // Then choose best node from different child-subtree
    int second_v = -1;
    int second_val = INT_MIN;

    for (int cid : touched) {
        if (cid == first_cid) continue;
        if (best_val[cid] > second_val) {
            second_val = best_val[cid];
            second_v = best_node[cid];
        }
    }

    if (second_v == -1) {
        // didn't find a second direction (should not happen if touched.size() >= 2, but we check)
        for (int cid : touched) {
            best_val[cid] = INT_MIN;
            best_node[cid] = -1;
        }
        return { NEG_INF, {} };
    }

    // Include these two endpoints
    sum += p[first_v];
    selected.push_back(first_v);
    sum += p[second_v];
    selected.push_back(second_v);

    // Add extra endpoints if allowed (C > 2)
    if (C > 2) {
        vector<int> rem;
        rem.reserve(boundary.size());
        for (int v : boundary) {
            if (v != first_v && v != second_v) {
                rem.push_back(v);
            }
        }

        int to_take = min((int)rem.size(), C - 2);  // already used 2 endpoints
        if (to_take > 0) {
            // get top to_take vertices by p[v] without fully sorting
            nth_element(rem.begin(), rem.begin() + to_take, rem.end(),
                        [&](int a, int b) { return p[a] > p[b]; });
            for (int i = 0; i < to_take; ++i) {
                sum += p[rem[i]];
                selected.push_back(rem[i]);
            }
        }
    }

    // Reset temporary arrays
    for (int cid : touched) {
        best_val[cid] = INT_MIN;
        best_node[cid] = -1;
    }

    return { sum, selected };
}

// ---------- Best subtree for odd D, center is an edge (u, v) ----------
pair<long long, vector<int>> best_subtree_from_edge_fast(
    int u, int v, const vector<int>& nodes, int D, int C
) {
    // Impossible if D=0 or we insist on only 1 endpoint
    if (D == 0 || C == 1) {
        return { NEG_INF, {} };
    }

    int target = (D - 1) / 2;   // distance from edge endpoints to diameter endpoints
    long long sum = p[u] + p[v];
    vector<int> selected;
    selected.push_back(u);
    selected.push_back(v);

    if (target == 0) {
        // D = 1: subtree is just the edge (u, v)
        return { sum, selected };
    }

    vector<int> bound_u, bound_v;
    bound_u.reserve(nodes.size());
    bound_v.reserve(nodes.size());

    // Classify nodes relative to closer endpoint of the central edge
    for (int w : nodes) {
        if (w == u || w == v) continue;
        int du = dist_all[u][w];
        int dv = dist_all[v][w];
        if (du < dv) {
            // w belongs to u-side
            if (du < target) {
                // interior on u-side
                sum += p[w];
                selected.push_back(w);
            } else if (du == target) {
                // boundary on u-side
                bound_u.push_back(w);
            }
        } else {
            // w belongs to v-side (dv <= du)
            if (dv < target) {
                sum += p[w];
                selected.push_back(w);
            } else if (dv == target) {
                bound_v.push_back(w);
            }
        }
    }

    // Need at least one boundary node on each side
    if (bound_u.empty() || bound_v.empty()) {
        return { NEG_INF, {} };
    }

    // Choose best boundary on u-side
    int bu = bound_u[0];
    for (int x : bound_u) {
        if (p[x] > p[bu]) bu = x;
    }
    // Choose best boundary on v-side
    int bv = bound_v[0];
    for (int x : bound_v) {
        if (p[x] > p[bv]) bv = x;
    }

    sum += p[bu];
    selected.push_back(bu);
    sum += p[bv];
    selected.push_back(bv);

    // Add extra endpoints if allowed
    if (C > 2) {
        vector<int> rem;
        rem.reserve(bound_u.size() + bound_v.size());
        for (int x : bound_u) {
            if (x != bu) rem.push_back(x);
        }
        for (int x : bound_v) {
            if (x != bv) rem.push_back(x);
        }
        int to_take = min((int)rem.size(), C - 2);
        if (to_take > 0) {
            nth_element(rem.begin(), rem.begin() + to_take, rem.end(),
                        [&](int a, int b) { return p[a] > p[b]; });
            for (int i = 0; i < to_take; ++i) {
                sum += p[rem[i]];
                selected.push_back(rem[i]);
            }
        }
    }

    return { sum, selected };
}

// ---------- Best subtree in a component (set of nodes) for given (D, C) ----------
pair<long long, vector<int>> best_subtree_in_component(
    const vector<int>& nodes, int D, int C
) {
    if (nodes.empty()) {
        return { NEG_INF, {} };
    }

    // Special case: D = 0, subtree is single vertex; pick best p
    if (D == 0 && C == 1) {
        int best_v = nodes[0];
        for (int v : nodes) {
            if (p[v] > p[best_v]) best_v = v;
        }
        return { (long long)p[best_v], vector<int>{best_v} };
    }

    long long best_sum = NEG_INF;
    vector<int> best_sel;

    if (D % 2 == 0) {
        // Even diameter: center is a vertex
        for (int root : nodes) {
            auto cur = best_subtree_from_root_fast(root, nodes, D, C);
            if (cur.first > best_sum) {
                best_sum = cur.first;
                best_sel = cur.second;
            }
        }
    } else {
        // Odd diameter: center is an edge
        vector<char> in_comp(n, 0);
        for (int v : nodes) in_comp[v] = 1;
        for (int u : nodes) {
            for (int v : adj[u]) {
                if (u < v && in_comp[v]) {
                    auto cur = best_subtree_from_edge_fast(u, v, nodes, D, C);
                    if (cur.first > best_sum) {
                        best_sum = cur.first;
                        best_sel = cur.second;
                    }
                }
            }
        }
    }

    return { best_sum, best_sel };
}

// ---------- Build a component when a split vertex is removed ----------
void get_component(int start, int split, vector<bool>& vis, vector<int>& comp) {
    // Iterative DFS or BFS is fine; here we do DFS recursion
    if (vis[start] || start == split) return;
    vis[start] = true;
    comp.push_back(start);
    for (int u : adj[start]) {
        if (!vis[u] && u != split) {
            get_component(u, split, vis, comp);
        }
    }
}

// ---------- Main solve ----------
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    precompute_all_pairs();

    long long total_sum = 0;
    for (int x : p) total_sum += x;

    long long best = NEG_INF;
    vector<int> best_selected_global;

    // Try each vertex as the "split" vertex that nobody takes
    for (int split = 0; split < n; ++split) {
        vector<bool> vis(n, false);
        vector<vector<int>> components;

        // From each neighbor of split, build a component (not crossing split)
        for (int u : adj[split]) {
            if (!vis[u]) {
                vector<int> comp;
                get_component(u, split, vis, comp);
                components.push_back(comp);
            }
        }

        int m = (int)components.size();
        if (m < 2) {
            // With this split, we can't host King and Queen in different components
            continue;
        }

        // For each component, compute best King-subtree and best Queen-subtree
        vector<pair<long long, vector<int>>> best1(m), best2(m);
        for (int i = 0; i < m; ++i) {
            best1[i] = best_subtree_in_component(components[i], d1, c1);
            best2[i] = best_subtree_in_component(components[i], d2, c2);
        }

        // Pair two different components: one for King, one for Queen
        for (int i = 0; i < m; ++i) {
            for (int j = i + 1; j < m; ++j) {
                auto [s1_i, sel1_i] = best1[i];
                auto [s2_i, sel2_i] = best2[i];
                auto [s1_j, sel1_j] = best1[j];
                auto [s2_j, sel2_j] = best2[j];

                // Option A: King in i, Queen in j
                if (s1_i > NEG_INF && s2_j > NEG_INF) {
                    long long total = s1_i + s2_j;
                    if (total > best) {
                        best = total;
                        best_selected_global.clear();
                        best_selected_global.insert(best_selected_global.end(), sel1_i.begin(), sel1_i.end());
                        best_selected_global.insert(best_selected_global.end(), sel2_j.begin(), sel2_j.end());
                    }
                }

                // Option B: King in j, Queen in i
                if (s2_i > NEG_INF && s1_j > NEG_INF) {
                    long long total = s2_i + s1_j;
                    if (total > best) {
                        best = total;
                        best_selected_global.clear();
                        best_selected_global.insert(best_selected_global.end(), sel2_i.begin(), sel2_i.end());
                        best_selected_global.insert(best_selected_global.end(), sel1_j.begin(), sel1_j.end());
                    }
                }
            }
        }
    }

    if (best < 0) {
        // No valid configuration found
        cout << -1 << "\n";
        return 0;
    }

    // Reconstruct destroyed nodes from best_selected_global
    vector<char> kept(n, 0);
    for (int v : best_selected_global) {
        kept[v] = 1;
    }

    long long cost = 0;
    vector<int> destroyed;
    for (int i = 0; i < n; ++i) {
        if (!kept[i]) {
            cost += p[i];
            destroyed.push_back(i + 1); // 1-based indexing for output
        }
    }

    sort(destroyed.begin(), destroyed.end());

    cout << cost << "\n";
    if (!destroyed.empty()) {
        for (int x : destroyed) cout << x << " ";
        cout << "\n";
    } else {
        cout << "\n";
    }

    return 0;
}
```

5. Python implementation with detailed comments
-----------------------------------------------

```python
import sys
from collections import deque

INF = 10**9
NEG_INF = -10**18

# ---------- Fast input ----------
def input():
    return sys.stdin.readline().strip()

# ---------- Read input ----------
n_line = input()
if not n_line:
    sys.exit(0)
n = int(n_line)

d1, c1, d2, c2 = map(int, input().split())
p = list(map(int, input().split()))
adj = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)

# ---------- Precompute all pairs shortest paths and first steps ----------
dist_all = [[INF] * n for _ in range(n)]
first_step = [[-1] * n for _ in range(n)]

for s in range(n):
    dist_all[s][s] = 0
    q = deque()
    # initialize neighbors
    for u in adj[s]:
        dist_all[s][u] = 1
        first_step[s][u] = u
        q.append(u)
    # BFS
    while q:
        v = q.popleft()
        dv = dist_all[s][v]
        for u in adj[v]:
            if dist_all[s][u] == INF:
                dist_all[s][u] = dv + 1
                first_step[s][u] = first_step[s][v]
                q.append(u)

# ---------- Best subtree for even D, center is root ----------
def best_subtree_from_root_fast(root, nodes, D, C):
    # D = 0: only subtree {root}
    if D == 0:
        if C >= 1:
            return p[root], [root]
        else:
            return NEG_INF, []
    # Need at least 2 endpoints for positive diameter
    if C == 1:
        return NEG_INF, []

    target = D // 2
    ssum = p[root]
    selected = [root]
    boundary = []

    for v in nodes:
        if v == root:
            continue
        dv = dist_all[root][v]
        if dv < target:
            ssum += p[v]
            selected.append(v)
        elif dv == target:
            boundary.append(v)

    if len(boundary) < 2:
        return NEG_INF, []

    # Group boundary by child-subtree (via first_step[root][v])
    best_val = {}   # child -> best cost
    best_node = {}  # child -> vertex

    for v in boundary:
        cid = first_step[root][v]
        if cid < 0:
            continue
        val = p[v]
        if cid not in best_val or val > best_val[cid]:
            best_val[cid] = val
            best_node[cid] = v

    if len(best_val) < 2:
        return NEG_INF, []

    # choose best boundary node overall
    first_cid = None
    first_v = None
    max_val = -1
    for cid, val in best_val.items():
        if val > max_val:
            max_val = val
            first_cid = cid
            first_v = best_node[cid]

    # choose best boundary from a different child
    second_v = None
    second_val = -1
    for cid, val in best_val.items():
        if cid == first_cid:
            continue
        if val > second_val:
            second_val = val
            second_v = best_node[cid]

    if second_v is None:
        return NEG_INF, []

    # include these two endpoints
    ssum += p[first_v]
    selected.append(first_v)
    ssum += p[second_v]
    selected.append(second_v)

    # add extra endpoints if allowed
    if C > 2:
        rem = [v for v in boundary if v != first_v and v != second_v]
        to_take = min(len(rem), C - 2)
        if to_take > 0:
            rem.sort(key=lambda x: p[x], reverse=True)
            for i in range(to_take):
                ssum += p[rem[i]]
                selected.append(rem[i])

    return ssum, selected

# ---------- Best subtree for odd D, center is edge (u, v) ----------
def best_subtree_from_edge_fast(u, v, nodes, D, C):
    if D == 0 or C == 1:
        return NEG_INF, []
    target = (D - 1) // 2
    ssum = p[u] + p[v]
    selected = [u, v]

    if target == 0:
        # diameter 1: just this edge
        return ssum, selected

    bound_u = []
    bound_v = []

    for w in nodes:
        if w == u or w == v:
            continue
        du = dist_all[u][w]
        dv = dist_all[v][w]
        if du < dv:
            # w on u-side
            if du < target:
                ssum += p[w]
                selected.append(w)
            elif du == target:
                bound_u.append(w)
        else:
            # w on v-side
            if dv < target:
                ssum += p[w]
                selected.append(w)
            elif dv == target:
                bound_v.append(w)

    if not bound_u or not bound_v:
        return NEG_INF, []

    bu = max(bound_u, key=lambda x: p[x])
    bv = max(bound_v, key=lambda x: p[x])

    ssum += p[bu]
    selected.append(bu)
    ssum += p[bv]
    selected.append(bv)

    if C > 2:
        rem = [x for x in bound_u if x != bu] + [x for x in bound_v if x != bv]
        to_take = min(len(rem), C - 2)
        if to_take > 0:
            rem.sort(key=lambda x: p[x], reverse=True)
            for i in range(to_take):
                ssum += p[rem[i]]
                selected.append(rem[i])

    return ssum, selected

# ---------- Best subtree in a component for given (D, C) ----------
def best_subtree_in_component(nodes, D, C):
    if not nodes:
        return NEG_INF, []

    # D = 0, C = 1: choose best single node
    if D == 0 and C == 1:
        best_v = max(nodes, key=lambda x: p[x])
        return p[best_v], [best_v]

    best_sum = NEG_INF
    best_sel = []

    if D % 2 == 0:
        # even diameter, vertex center
        for root in nodes:
            cur_sum, cur_sel = best_subtree_from_root_fast(root, nodes, D, C)
            if cur_sum > best_sum:
                best_sum = cur_sum
                best_sel = cur_sel
    else:
        # odd diameter, edge center
        in_comp = [False] * n
        for v in nodes:
            in_comp[v] = True
        for u in nodes:
            for v in adj[u]:
                if u < v and in_comp[v]:
                    cur_sum, cur_sel = best_subtree_from_edge_fast(u, v, nodes, D, C)
                    if cur_sum > best_sum:
                        best_sum = cur_sum
                        best_sel = cur_sel

    return best_sum, best_sel

# ---------- Build one component when split is removed ----------
def get_component(start, split, vis):
    stack = [start]
    comp = []
    while stack:
        v = stack.pop()
        if vis[v] or v == split:
            continue
        vis[v] = True
        comp.append(v)
        for u in adj[v]:
            if not vis[u] and u != split:
                stack.append(u)
    return comp

# ---------- Main solve ----------
total_sum = sum(p)
best = NEG_INF
best_selected_global = None

# Try each vertex as the split
for split in range(n):
    vis = [False] * n
    components = []

    # neighbors of split start components
    for u in adj[split]:
        if not vis[u]:
            comp = get_component(u, split, vis)
            components.append(comp)

    m = len(components)
    if m < 2:
        continue

    best1 = [None] * m
    best2 = [None] * m
    for i, comp in enumerate(components):
        best1[i] = best_subtree_in_component(comp, d1, c1)
        best2[i] = best_subtree_in_component(comp, d2, c2)

    # pair components: one for King, one for Queen
    for i in range(m):
        for j in range(i + 1, m):
            s1_i, sel1_i = best1[i]
            s2_i, sel2_i = best2[i]
            s1_j, sel1_j = best1[j]
            s2_j, sel2_j = best2[j]

            # King in i, Queen in j
            if s1_i > NEG_INF and s2_j > NEG_INF:
                total = s1_i + s2_j
                if total > best:
                    best = total
                    best_selected_global = sel1_i + sel2_j

            # King in j, Queen in i
            if s2_i > NEG_INF and s1_j > NEG_INF:
                total = s2_i + s1_j
                if total > best:
                    best = total
                    best_selected_global = sel2_i + sel1_j

# ---------- Output ----------
if best < 0 or best_selected_global is None:
    print(-1)
else:
    kept = [False] * n
    for v in best_selected_global:
        kept[v] = True

    destroyed = []
    cost = 0
    for i in range(n):
        if not kept[i]:
            destroyed.append(i + 1)  # 1-based
            cost += p[i]

    destroyed.sort()
    print(cost)
    if destroyed:
        print(" ".join(map(str, destroyed)))
    else:
        print()
```

This Python implementation follows exactly the same logic as the C++ solution and runs in `O(n^3)` with `n ≤ 200`, which is well within the problem’s limits.