Training
The graph consists of a tree plus additional non-tree edges, each with a removal cost. We want to delete a minimum-cost set of non-tree edges so that the remaining graph contains no even cycle.
Problem Statement
Rendered from the "Problem Summary" section in the LaTeX write-up.
The graph consists of a tree plus additional non-tree edges, each with a removal cost. We want to delete a minimum-cost set of non-tree edges so that the remaining graph contains no even cycle.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Structural Reduction
For a non-tree edge $e=(u,v)$, let $TP(e)$ be the unique tree path between $u$ and $v$.
If $|TP(e)|$ is odd, then $e \cup TP(e)$ is an even cycle, so $e$ can never be kept.
If $|TP(e)|$ is even, then $e \cup TP(e)$ is an odd cycle. Such an edge may be kept.
The key fact from the official solution is:
Two keepable edges can be chosen together if and only if their tree paths are edge-disjoint.
So the task becomes:
choose a maximum-weight subset of keepable non-tree edges whose tree paths are pairwise edge-disjoint.
DP State
Root the tree. For each node $v$, let its children be indexed from $0$ to $d-1$. Because the maximum degree is at most $10$, we can use bitmasks on the children of $v$.
Define \[ dp[v][mask] \] as the maximum total kept weight inside the component rooted at $v$ after removing the child-edges whose bits are set in $mask$.
The base value is: \[ dp[v][mask] = \sum_{\text{child } c_i \notin mask} dp[c_i][0], \] which corresponds to choosing no path that passes through $v$.
Transition
Group every keepable non-tree edge by its LCA. Consider one such edge $e=(a,b)$ with $\mathrm{LCA}(a,b)=v$. Its tree path uses one or two child-edges of $v$; let the corresponding bitmask be $rootMask(e)$.
If we keep $e$, then:
the child-edges in $rootMask(e)$ become unavailable at $v$;
every node strictly below $v$ on the two root-to-endpoint branches becomes the root of an independent subproblem where exactly one child-edge (the one continuing along the path) is removed;
each endpoint contributes a full subtree state $dp[x][0]$.
All branch contributions are independent of the current $mask$, so for every edge $e$ we can precompute a constant \[ extra(e). \] Then the transition is simply \[ dp[v][mask] = \max\bigl(dp[v][mask],\ extra(e) + dp[v][mask \cup rootMask(e)]\bigr). \]
Since the right-hand side uses a strict superset of $mask$, we evaluate masks in decreasing order.
Complexity
Let $K \le 10$ be the maximum degree.
States: $O\!\left(\sum_v 2^{\deg(v)}\right)$.
Transitions: $O(MN + M2^K)$, matching the official bound.
Space: $O\!\left(\sum_v 2^{\deg(v)}\right)$.
Finally, if $W$ is the sum of all non-tree edge weights and $best = dp[root][0]$ is the maximum keepable weight, the minimum removed cost is $W - best$.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
struct ExtraEdge {
int u;
int v;
long long w;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
vector<vector<int>> tree_adj(N + 1);
vector<int> eu(M), ev(M);
vector<long long> ew(M);
for (int i = 0; i < N - 1; ++i) {
cin >> eu[i] >> ev[i] >> ew[i];
tree_adj[eu[i]].push_back(ev[i]);
tree_adj[ev[i]].push_back(eu[i]);
}
for (int i = N - 1; i < M; ++i) {
cin >> eu[i] >> ev[i] >> ew[i];
}
vector<int> parent(N + 1, 0), depth(N + 1, 0), index_in_parent(N + 1, -1);
vector<vector<int>> children(N + 1);
vector<int> order;
order.reserve(N);
queue<int> q;
q.push(1);
parent[1] = -1;
while (!q.empty()) {
int v = q.front();
q.pop();
order.push_back(v);
for (int to : tree_adj[v]) {
if (to == parent[v]) continue;
parent[to] = v;
depth[to] = depth[v] + 1;
index_in_parent[to] = (int)children[v].size();
children[v].push_back(to);
q.push(to);
}
}
int LOG = 1;
while ((1 << LOG) <= N) ++LOG;
vector<vector<int>> up(LOG, vector<int>(N + 1, 0));
for (int v = 1; v <= N; ++v) up[0][v] = max(parent[v], 0);
for (int k = 1; k < LOG; ++k) {
for (int v = 1; v <= N; ++v) up[k][v] = up[k - 1][up[k - 1][v]];
}
auto lca = [&](int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
int diff = depth[a] - depth[b];
for (int k = LOG - 1; k >= 0; --k) {
if (diff & (1 << k)) a = up[k][a];
}
if (a == b) return a;
for (int k = LOG - 1; k >= 0; --k) {
if (up[k][a] != up[k][b]) {
a = up[k][a];
b = up[k][b];
}
}
return parent[a];
};
long long total_extra_weight = 0;
vector<vector<ExtraEdge>> edges_at_lca(N + 1);
for (int i = N - 1; i < M; ++i) {
total_extra_weight += ew[i];
if ((depth[eu[i]] ^ depth[ev[i]]) & 1) continue;
int w = lca(eu[i], ev[i]);
edges_at_lca[w].push_back({eu[i], ev[i], ew[i]});
}
vector<vector<long long>> dp(N + 1);
auto branch_info = [&](int root, int endpoint) {
pair<int, long long> result{-1, 0};
if (endpoint == root) return result;
int cur = endpoint;
int prev = -1;
long long contrib = 0;
while (cur != root) {
if (prev == -1) {
contrib += dp[cur][0];
} else {
contrib += dp[cur][1 << index_in_parent[prev]];
}
prev = cur;
cur = parent[cur];
}
result.first = index_in_parent[prev];
result.second = contrib;
return result;
};
for (int it = (int)order.size() - 1; it >= 0; --it) {
int v = order[it];
int deg = (int)children[v].size();
int states = 1 << deg;
dp[v].assign(states, 0);
vector<long long> removed_sum(states, 0);
for (int mask = 1; mask < states; ++mask) {
int bit = __builtin_ctz(mask);
removed_sum[mask] =
removed_sum[mask ^ (1 << bit)] + dp[children[v][bit]][0];
}
long long total_child_sum = removed_sum[states - 1];
for (int mask = states - 1; mask >= 0; --mask) {
dp[v][mask] = total_child_sum - removed_sum[mask];
}
struct Transition {
int branch_mask;
long long extra;
};
vector<Transition> trans;
trans.reserve(edges_at_lca[v].size());
for (const ExtraEdge &e : edges_at_lca[v]) {
auto left = branch_info(v, e.u);
auto right = branch_info(v, e.v);
int branch_mask = 0;
if (left.first != -1) branch_mask |= 1 << left.first;
if (right.first != -1) branch_mask |= 1 << right.first;
long long extra = e.w + left.second + right.second;
trans.push_back({branch_mask, extra});
}
for (int mask = states - 1; mask >= 0; --mask) {
for (const Transition &tr : trans) {
if (mask & tr.branch_mask) continue;
dp[v][mask] = max(dp[v][mask], tr.extra + dp[v][mask | tr.branch_mask]);
}
}
}
cout << total_extra_weight - dp[1][0] << '\n';
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.