alright
time for this unholy problem
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:
- 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
- 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
#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;
}