back to home

problem link

berland federalization

alright
time for this unholy problem

oh my god i want to kill the author of this

not even joking
this problem was so hecking hard

but anyways, i want to make you suffer less on this problem if you decide to give up
so we have a normal tree w/ at most 400 nodes and we want to find a subtree of k nodes such that the number of edges connecting it to the rest of the tree is minimal

this is a tree dp problem, and the definition is easy- it's basically as dumb as you can get:

``` dp[n][k] = min edge set that connects a subtree of size k rooted at n to the rest of the tree (undefined if impossible) ```

the hard part is transition and implementing-

ac
actually
now that i think about it this problem wasn't even that bad i was just smol brain

so for the transition the base cases are these:

``` dp[n][0] = {} dp[n][1] = {} ```

then we go through each subtree, and add their dp array to the current one
and for each subtree, we have two main choices:

  1. we don't include any of it, and add the edge connecting it and the current root to the current edge set we're processing
  2. we include some of it, and add the stuff stored in that portion's dp array

that's it for the main algorithm, the rest is implementation crap so just here's the code

```cpp #include <iostream> #include <cassert> #include <vector> #include <set> #include <algorithm> using std::cout; using std::endl; using std::vector; using std::pair; class Country { private: struct Road { int from; int to; bool operator==(const Road& o) { return (from == o.from && to == o.to) || (from == o.to && to == o.from); } }; static const int ROOT = 0; const vector<vector<int>>& neighbors; int target_size; vector<int> sub_town_num; vector<int> parent; /* * this[n][k] = min problem roads given that * there is a k-sized town rooted at n * the stored vector is a list of the supposed "problem" roads * min_roads just contains the size/validity of each state for convenience */ vector<vector<vector<Road>>> best; vector<vector<int>> min_roads; void process_towns(int at, int prev) { sub_town_num[at] = 1; parent[at] = prev; // preliminary calculations for (int n : neighbors[at]) { if (n != prev) { process_towns(n, at); sub_town_num[at] += sub_town_num[n]; } } /* * ok so this base case isn't really true, but if the parent wants * to include none from this subtree they have to cut off this road * so might as well include it now */ best[at][0] = {{at, prev}}; min_roads[at][0] = 1; best[at][1] = {}; min_roads[at][1] = 0; // then incorporate the child towns for (int n : neighbors[at]) { if (n == prev) { continue; } vector<vector<Road>> new_b(target_size + 1); vector<int> new_m(target_size + 1, INT32_MAX); new_b[0] = best[at][0]; new_m[0] = min_roads[at][0]; // go through each state for this node and see // how much of the current subtree and neighbor to include for (int st = 1; st <= target_size; st++) { for (int at_amt = 1; at_amt <= st; at_amt++) { int n_amt = st - at_amt; if (min_roads[at][at_amt] == INT32_MAX || min_roads[n][n_amt] == INT32_MAX) { continue; } int new_r = min_roads[at][at_amt] + min_roads[n][n_amt]; if (new_r < new_m[st]) { new_m[st] = new_r; new_b[st] = vector<Road>(best[at][at_amt]); new_b[st].insert( new_b[st].end(), best[n][n_amt].begin(), best[n][n_amt].end() ); } } } best[at] = new_b; min_roads[at] = new_m; } if (sub_town_num[at] <= target_size) { // or the entire subtree could be a state lol best[at][sub_town_num[at]] = {}; } } public: // i honestly don't know if the formatting for this is correct or not lmao Country(const vector<vector<int>>& neighbors, int target_size) : neighbors(neighbors), target_size(target_size), sub_town_num(neighbors.size()), parent(neighbors.size()), best(neighbors.size(), vector<vector<Road>>(target_size + 1)), min_roads(neighbors.size(), vector<int>(target_size + 1, INT32_MAX)) { assert(target_size >= 1); // this breaks down for any other number lol process_towns(ROOT, ROOT); } vector<Road> min_problem_roads() { int min_problem_amt = INT32_MAX; vector<Road> town_roads; for (int r = 0; r < neighbors.size(); r++) { if (min_roads[r][target_size] == INT32_MAX) { continue; } if (r == ROOT) { if (min_roads[r][target_size] < min_problem_amt) { min_problem_amt = min_roads[r][target_size]; town_roads = best[r][target_size]; } } else { // so if this node isn't the root, the edge connecting it // and its parent also needs to be considered if (min_roads[r][target_size] + 1 < min_problem_amt) { min_problem_amt = min_roads[r][target_size] + 1; town_roads = best[r][target_size]; town_roads.push_back({r, parent[r]}); } } } return town_roads; } }; /** * https://codeforces.com/contest/440/problem/D * 5 2 * 1 2 * 1 3 * 1 4 * 1 5 should output * 2 * 3 4 */ int main() { int town_num; int target_size; std::cin >> town_num >> target_size; vector<vector<int>> neighbors(town_num); vector<pair<int, int>> roads; for (int e = 0; e < town_num - 1; e++) { int from; int to; std::cin >> from >> to; neighbors[--from].push_back(--to); neighbors[to].push_back(from); roads.push_back({from, to}); } Country country(neighbors, target_size); std::set<pair<int, int>> to_remove; for (const auto& r : country.min_problem_roads()) { to_remove.insert({r.from, r.to}); } vector<int> remove_ind; for (int r = 0; r < town_num - 1; r++) { // append the indices of all roads that are in the "to remove" list if (to_remove.count(roads[r]) || to_remove.count(std::make_pair(roads[r].second, roads[r].first))) { remove_ind.push_back(r); } } cout << remove_ind.size() << endl; for (int i = 0; i < (int) remove_ind.size() - 1; i++) { cout << remove_ind[i] + 1 << ' '; } if (!remove_ind.empty()) { cout << remove_ind.back() + 1; } cout << endl; } ```