<|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
-------------------------

### 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 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.

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

6. Else:

   - Mark all nodes in the best selection as "kept".
   - All others (including the selected `split` and any unused nodes) are destroyed.

   - Destruction cost is `total_sum - best`.

   - 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)`:

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

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

#### 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.
   - Else if `dv == target`: boundary node, collect into a `boundary` list.
4. If `boundary.size() < 2`: skip this root.
5. Group boundary nodes by child of `root` they pass through (via `first_step[root][v]`). Need candidates from at least 2 distinct child-subtrees.
6. Pick mandatory endpoints: best boundary node overall (`first_v`) and best from a different child (`second_v`). Include both.
7. If `C > 2`, add up to `C - 2` more boundary nodes by highest `p[v]`.
8. Keep the best `(ssum, selected)` over all roots.

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

For each edge `(u, v)` completely inside the component:

1. `target = R = (D - 1) // 2`.
2. Start with `u` and `v` included.
3. If `target == 0` (D = 1): return `{u, v}`.
4. For every other node `w`:
   - Assign to closer side (u-side if `du < dv`, else v-side).
   - Interior (distance < target): include.
   - Boundary (distance == target): add to `bound_u` or `bound_v`.
5. Must have at least one boundary node on each side.
6. Pick `bu` (best in `bound_u`) and `bv` (best in `bound_v`). Include both.
7. If `C > 2`, add up to `C - 2` more from remaining boundary nodes.
8. Track maximal `(ssum, selected)` over all edges.


4. C++ Solution
---------------

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const int64_t inf = 1e18;

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

void read() {
    cin >> n >> d1 >> c1 >> d2 >> c2;
    p.resize(n);
    cin >> p;
    adj.resize(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);
    }
}

void precompute_all_pairs() {
    dist_all.assign(n, vector<int>(n, INT_MAX));
    first_step.assign(n, vector<int>(n, -1));
    queue<int> q;
    for(int s = 0; s < n; s++) {
        while(!q.empty()) {
            q.pop();
        }
        dist_all[s][s] = 0;
        for(int u: adj[s]) {
            dist_all[s][u] = 1;
            first_step[s][u] = u;
            q.push(u);
        }
        while(!q.empty()) {
            int v = q.front();
            q.pop();
            for(int u: adj[v]) {
                if(dist_all[s][u] == INT_MAX) {
                    dist_all[s][u] = dist_all[s][v] + 1;
                    first_step[s][u] = first_step[s][v];
                    q.push(u);
                }
            }
        }
    }
}

pair<int64_t, vector<int>> best_subtree_from_root_fast(
    int root, const vector<int>& nodes, int d, int c
) {
    if(d == 0) {
        return c >= 1 ? make_pair((int64_t)p[root], vector<int>{root})
                      : make_pair(-inf, vector<int>{});
    }
    if(c == 1) {
        return {-inf, {}};
    }

    int target = d / 2;
    int64_t sum = p[root];
    vector<int> selected = {root};
    vector<int> boundary;
    boundary.reserve(nodes.size());

    for(int v: nodes) {
        if(v == root) {
            continue;
        }
        int dv = dist_all[root][v];
        if(dv < target) {
            sum += p[v];
            selected.push_back(v);
        } else if(dv == target) {
            boundary.push_back(v);
        }
    }

    if(boundary.size() < 2) {
        return make_pair(-inf, vector<int>{});
    }

    static vector<int> best_val, best_node;
    if((int)best_val.size() < n) {
        best_val.assign(n, INT_MIN);
        best_node.assign(n, -1);
    }
    vector<int> touched;
    touched.reserve(adj[root].size());
    for(int v: boundary) {
        int cid = first_step[root][v];
        if(cid < 0) {
            continue;
        }
        if(p[v] > best_val[cid]) {
            if(best_node[cid] == -1) {
                touched.push_back(cid);
            }
            best_val[cid] = p[v];
            best_node[cid] = v;
        }
    }
    if(touched.size() < 2) {
        for(int cid: touched) {
            best_val[cid] = INT_MIN;
            best_node[cid] = -1;
        }
        return {-inf, {}};
    }

    int first_cid = -1, first_v = -1, fv = INT_MIN;
    for(int cid: touched) {
        if(best_val[cid] > fv) {
            fv = best_val[cid];
            first_cid = cid;
            first_v = best_node[cid];
        }
    }
    int second_v = -1, sv = INT_MIN;
    for(int cid: touched) {
        if(cid != first_cid && best_val[cid] > sv) {
            sv = best_val[cid];
            second_v = best_node[cid];
        }
    }
    if(second_v == -1) {
        for(int cid: touched) {
            best_val[cid] = INT_MIN;
            best_node[cid] = -1;
        }
        return {-inf, {}};
    }
    sum += p[first_v];
    selected.push_back(first_v);
    sum += p[second_v];
    selected.push_back(second_v);

    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);
        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]);
            }
        }
    }
    for(int cid: touched) {
        best_val[cid] = INT_MIN;
        best_node[cid] = -1;
    }
    return {sum, selected};
}

pair<int64_t, vector<int>> best_subtree_from_edge_fast(
    int u, int v, const vector<int>& nodes, int d, int c
) {
    if(d == 0 || c == 1) {
        return {-inf, {}};
    }
    int target = (d - 1) / 2;
    int64_t sum = p[u] + p[v];
    vector<int> selected = {u, v};
    if(target == 0) {
        return {sum, selected};
    }

    vector<int> bound_u, bound_v;
    bound_u.reserve(nodes.size());
    bound_v.reserve(nodes.size());
    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) {
            if(du < target) {
                sum += p[w];
                selected.push_back(w);
            } else if(du == target) {
                bound_u.push_back(w);
            }
        } else {
            if(dv < target) {
                sum += p[w];
                selected.push_back(w);
            } else if(dv == target) {
                bound_v.push_back(w);
            }
        }
    }
    if(bound_u.empty() || bound_v.empty()) {
        return {-inf, {}};
    }
    int bu = bound_u[0];
    for(int x: bound_u) {
        if(p[x] > p[bu]) {
            bu = x;
        }
    }
    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);
    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};
}

void dfs_collect(
    int v, int par, int dist, int split, vector<vector<int>>& by_dist,
    int max_dist
) {
    if(v == split) {
        return;
    }
    if(dist > max_dist) {
        return;
    }
    if(dist >= by_dist.size()) {
        by_dist.resize(dist + 1);
    }
    by_dist[dist].push_back(v);
    for(int u: adj[v]) {
        if(u != par && u != split) {
            dfs_collect(u, v, dist + 1, split, by_dist, max_dist);
        }
    }
}

void dfs_mark_subtree(
    int v, int par, int dist, int split, int subtree_id,
    vector<vector<int>>& by_dist, vector<int>& subtree_mark, int max_dist
) {
    if(v == split) {
        return;
    }
    if(dist > max_dist) {
        return;
    }
    if(dist >= by_dist.size()) {
        by_dist.resize(dist + 1);
    }
    by_dist[dist].push_back(v);
    subtree_mark[v] = subtree_id;
    for(int u: adj[v]) {
        if(u != par && u != split) {
            dfs_mark_subtree(
                u, v, dist + 1, split, subtree_id, by_dist, subtree_mark,
                max_dist
            );
        }
    }
}

pair<int64_t, vector<int>> best_subtree_from_root(
    int root, int split, int d, int c
) {
    if(d == 0) {
        return c >= 1 ? make_pair((int64_t)p[root], vector<int>{root})
                      : make_pair(-inf, vector<int>{});
    }
    if(c == 1) {
        return {-inf, {}};
    }

    vector<vector<int>> by_dist;
    vector<int> subtree_mark(n, -1);

    int subtree_id = 0;
    for(int child: adj[root]) {
        if(child != split) {
            dfs_mark_subtree(
                child, root, 1, split, subtree_id++, by_dist, subtree_mark,
                d / 2
            );
        }
    }

    if(by_dist.empty()) {
        return {-inf, {}};
    }

    subtree_mark[root] = -1;

    int64_t sum = p[root];
    vector<int> selected = {root};
    int target_dist = d / 2;

    for(int dist = 1; dist < by_dist.size() && dist < target_dist; dist++) {
        for(int v: by_dist[dist]) {
            sum += p[v];
            selected.push_back(v);
        }
    }

    if(target_dist < by_dist.size()) {
        vector<int>& cands = by_dist[target_dist];

        if(d > 0) {
            if((int)cands.size() < 2) {
                return {-inf, {}};
            }

            vector<pair<int, int>> best_per(subtree_id, {INT_MIN, -1});
            int distinct = 0;
            for(int v: cands) {
                int sid = subtree_mark[v];
                if(sid < 0 || sid >= subtree_id) {
                    continue;
                }
                if(p[v] > best_per[sid].first) {
                    if(best_per[sid].second == -1) {
                        distinct++;
                    }
                    best_per[sid] = {p[v], v};
                }
            }
            if(distinct < 2) {
                return {-inf, {}};
            }

            int first_subtree = -1, first_v = -1, best_val = INT_MIN;
            for(int sid = 0; sid < subtree_id; sid++) {
                if(best_per[sid].second == -1) {
                    continue;
                }
                if(best_per[sid].first > best_val) {
                    best_val = best_per[sid].first;
                    first_subtree = sid;
                    first_v = best_per[sid].second;
                }
            }
            sum += p[first_v];
            selected.push_back(first_v);

            int second_v = -1, second_val = INT_MIN;
            for(int sid = 0; sid < subtree_id; sid++) {
                if(sid == first_subtree) {
                    continue;
                }
                if(best_per[sid].second == -1) {
                    continue;
                }
                if(best_per[sid].first > second_val) {
                    second_val = best_per[sid].first;
                    second_v = best_per[sid].second;
                }
            }
            if(second_v == -1) {
                return {-inf, {}};
            }
            sum += p[second_v];
            selected.push_back(second_v);

            if(c > 2) {
                vector<int> rem;
                rem.reserve(cands.size());
                for(int v: cands) {
                    if(v != first_v && v != second_v) {
                        rem.push_back(v);
                    }
                }
                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]);
                    }
                }
            }
        } else {
            int to_select = min((int)cands.size(), c);
            if(to_select > 0) {
                nth_element(
                    cands.begin(), cands.begin() + to_select, cands.end(),
                    [](int a, int b) { return p[a] > p[b]; }
                );
            }
            for(int i = 0; i < to_select; i++) {
                sum += p[cands[i]];
                selected.push_back(cands[i]);
            }
        }
    } else {
        return {-inf, {}};
    }

    return {sum, selected};
}

pair<int64_t, vector<int>> best_subtree_from_edge(
    int u, int v, int split, int d, int c
) {
    if(d == 0 || c == 1) {
        return {-inf, {}};
    }
    if(u == split || v == split) {
        return {-inf, {}};
    }

    vector<vector<int>> by_dist_u, by_dist_v;
    dfs_collect(u, v, 0, split, by_dist_u, (d - 1) / 2);
    dfs_collect(v, u, 0, split, by_dist_v, (d - 1) / 2);

    int64_t sum = p[u] + p[v];
    vector<int> selected = {u, v};
    int target_dist = (d - 1) / 2;

    if(target_dist == 0) {
        return {sum, selected};
    }

    for(int dist = 1; dist < target_dist; dist++) {
        if(dist < by_dist_u.size()) {
            for(int w: by_dist_u[dist]) {
                sum += p[w];
                selected.push_back(w);
            }
        }
        if(dist < by_dist_v.size()) {
            for(int w: by_dist_v[dist]) {
                sum += p[w];
                selected.push_back(w);
            }
        }
    }

    vector<int> cands_u, cands_v;
    if(target_dist < by_dist_u.size()) {
        cands_u = by_dist_u[target_dist];
    }
    if(target_dist < by_dist_v.size()) {
        cands_v = by_dist_v[target_dist];
    }

    if(cands_u.empty() || cands_v.empty()) {
        return {-inf, {}};
    }

    int best_u = cands_u[0];
    for(int x: cands_u) {
        if(p[x] > p[best_u]) {
            best_u = x;
        }
    }
    int best_v = cands_v[0];
    for(int x: cands_v) {
        if(p[x] > p[best_v]) {
            best_v = x;
        }
    }

    sum += p[best_u];
    selected.push_back(best_u);
    sum += p[best_v];
    selected.push_back(best_v);

    if(c > 2) {
        vector<int> rem;
        rem.reserve((int)cands_u.size() + (int)cands_v.size());
        for(int x: cands_u) {
            if(x != best_u) {
                rem.push_back(x);
            }
        }
        for(int x: cands_v) {
            if(x != best_v) {
                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};
}

pair<int64_t, vector<int>> best_subtree_in_component(
    const vector<int>& nodes, int split, int d, int c
) {
    if(nodes.empty()) {
        return {-inf, {}};
    }

    if(d == 0 && c == 1) {
        int64_t res = -inf;
        int best = -1;
        for(int v: nodes) {
            if(p[v] > res) {
                res = p[v];
                best = v;
            }
        }
        return {res, {best}};
    }

    pair<int64_t, vector<int>> res = {-inf, {}};

    if(d % 2 == 0) {
        for(int root: nodes) {
            auto cur = best_subtree_from_root_fast(root, nodes, d, c);
            if(cur.first > res.first) {
                res = cur;
            }
        }
    } else {
        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 > res.first) {
                        res = cur;
                    }
                }
            }
        }
    }

    return res;
}

void get_component(int v, int split, vector<bool>& vis, vector<int>& comp) {
    if(vis[v] || v == split) {
        return;
    }
    vis[v] = true;
    comp.push_back(v);
    for(int u: adj[v]) {
        get_component(u, split, vis, comp);
    }
}

void solve() {
    // The problem asks us to choose two subtrees that don't touch each other
    // and have the largest sum of p[i] of selected vertices (final answer is
    // sum(p) - sum(selected p)). The two trees have constraints in terms of the
    // diameters they have (D1 and D2), and the number of diameter endpoints (C1
    // and C2). The way to start with this problem is to see that n is fairly
    // small - it can be up to 200.
    //
    // We will start by trying every possible "splitting vertex". In other
    // words, we will try to explicitly delete each node. This splits the tree
    // into two smaller trees T1 and T2. We will then try the two options - D1
    // and C1 in T1, and D1 and C1 in T2 (and similarly D2 and C2 in the
    // opposite).
    //
    // The problem is now simpler - given a tree T, find the subtree with
    // largest sum that has diameter D and C diameter endpoints. The easiest way
    // to solve this is to consider two cases:
    //     1) D is even. This means that there is a center node Q for any valid
    //        subtree. We will try every possible vertex Q, do a DFS with Q as
    //        the root and for each node. This partitions all other nodes in
    //        groups based on the distance from Q to them. The strategy
    //        afterwards is simple - we will take all nodes with distance < D
    //        / 2. For distance exactly D / 2, to ensure diameter is actually D,
    //        we must select nodes from at least 2 different child subtrees of
    //        Q. We mark each node by which child subtree it belongs to, then
    //        greedily select the largest node from each subtree (guaranteeing
    //        2+ subtrees), then fill remaining slots up to C with the largest
    //        remaining nodes.
    //     2) D is odd. For this to be the case C > 1 (otherwise impossible). We
    //        will do something similar to case (1), but we will try to select
    //        an edge, or two adjacent vertices Q1 and Q2. We will do DFS from
    //        both (with parent being Q1, Q2, so that we visit only the
    //        corresponding parts of the tree). Essentially, we want to select
    //        all nodes at distance < (D - 1) / 2. When it comes to distance
    //        exactly (D - 1) / 2, we will select the two largest nodes from
    //        both sides, and then from the rest of the nodes select the largest
    //        (C - 2). This can be done with nth_element again, to avoid
    //        sorting.
    //
    // The is also one special case. C = 1 and D = 0. If C = 1 and D > 0 or D =
    // 0, and C != 1, it's impossible. In this special case, we can select a
    // single node, so we just get the maximum p[] value.
    //
    // Overall, if implemented properly, the time complexity is O(N^3). In terms
    // of implementation, to make it clean we can share a lot of the code
    // between the two cases. Implementing well requires a series of
    // precomputes.

    int64_t total_sum = 0;
    for(int x: p) {
        total_sum += x;
    }

    int64_t best = -inf;
    int best_split = -1;
    vector<int> best_selected;

    for(int split = 0; split < n; split++) {
        vector<bool> vis(n);
        vector<vector<int>> components;

        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();
        vector<pair<int64_t, vector<int>>> best1(m), best2(m);
        for(int i = 0; i < m; i++) {
            best1[i] = best_subtree_in_component(components[i], split, d1, c1);
            best2[i] = best_subtree_in_component(components[i], split, d2, c2);
        }

        for(int i = 0; i < m; i++) {
            for(int j = i + 1; j < m; j++) {
                int64_t total = best1[i].first + best2[j].first;
                if(total > best) {
                    best = total;
                    best_split = split;
                    best_selected = best1[i].second;
                    best_selected.insert(
                        best_selected.end(), best2[j].second.begin(),
                        best2[j].second.end()
                    );
                }
                total = best2[i].first + best1[j].first;
                if(total > best) {
                    best = total;
                    best_split = split;
                    best_selected = best2[i].second;
                    best_selected.insert(
                        best_selected.end(), best1[j].second.begin(),
                        best1[j].second.end()
                    );
                }
            }
        }
    }

    if(best < 0) {
        cout << -1 << "\n";
    } else {
        vector<bool> kept(n);
        for(int v: best_selected) {
            kept[v] = true;
        }

        vector<int> destroyed;
        int64_t cost = 0;
        for(int i = 0; i < n; i++) {
            if(!kept[i]) {
                destroyed.push_back(i + 1);
                cost += p[i];
            }
        }

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        precompute_all_pairs();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Solution
------------------

```python
import sys
from collections import deque
from math import inf

def input():
    return sys.stdin.readline().strip()

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)

dist_all = [[10**9] * n for _ in range(n)]
first_step = [[-1] * n for _ in range(n)]

for s in range(n):
    q = deque()
    dist_all[s][s] = 0
    for u in adj[s]:
        dist_all[s][u] = 1
        first_step[s][u] = u
        q.append(u)
    while q:
        v = q.popleft()
        dv = dist_all[s][v]
        for u in adj[v]:
            if dist_all[s][u] == 10**9:
                dist_all[s][u] = dv + 1
                first_step[s][u] = first_step[s][v]
                q.append(u)

NEG_INF = -10**18

def best_subtree_from_root_fast(root, nodes, d, c):
    if d == 0:
        if c >= 1:
            return p[root], [root]
        else:
            return NEG_INF, []
    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, []

    best_val = {}
    best_node = {}

    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, []

    first_cid, first_v = None, None
    fv = -10**9
    for cid, val in best_val.items():
        if val > fv:
            fv = val
            first_cid = cid
            first_v = best_node[cid]

    second_v = None
    sv = -10**9
    for cid, val in best_val.items():
        if cid == first_cid:
            continue
        if val > sv:
            sv = val
            second_v = best_node[cid]

    if second_v is None:
        return NEG_INF, []

    ssum += p[first_v]
    selected.append(first_v)
    ssum += p[second_v]
    selected.append(second_v)

    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

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:
        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:
            if du < target:
                ssum += p[w]
                selected.append(w)
            elif du == target:
                bound_u.append(w)
        else:
            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

def best_subtree_in_component(nodes, d, c):
    if not nodes:
        return NEG_INF, []

    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:
        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:
        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

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

total_sum = sum(p)

best = NEG_INF
best_selected_global = None

for split in range(n):
    vis = [False] * n
    components = []

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

    m = len(components)
    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)

    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]

            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

            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

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)
            cost += p[i]

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