IOI 2007 - Training

#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;
}

\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb}
\usepackage{listings}
\usepackage{xcolor}

\lstset{
  language=C++,
  basicstyle=\ttfamily\small,
  keywordstyle=\color{blue}\bfseries,
  commentstyle=\color{gray},
  numbers=left,
  numberstyle=\tiny\color{gray},
  breaklines=true,
  frame=single,
  tabsize=4,
  showstringspaces=false
}

\title{IOI 2007 -- Training}
\author{Solution}
\date{}

\begin{document}
\maketitle

\section{Problem Summary}
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 \emph{no even cycle}.

\section{Structural Reduction}
For a non-tree edge $e=(u,v)$, let $TP(e)$ be the unique tree path between $u$ and $v$.

\begin{itemize}
  \item If $|TP(e)|$ is odd, then $e \cup TP(e)$ is an even cycle, so $e$ can never be kept.
  \item If $|TP(e)|$ is even, then $e \cup TP(e)$ is an odd cycle. Such an edge may be kept.
\end{itemize}

The key fact from the official solution is:
\begin{quote}
Two keepable edges can be chosen together if and only if their tree paths are edge-disjoint.
\end{quote}

So the task becomes:
\begin{center}
\emph{choose a maximum-weight subset of keepable non-tree edges whose tree paths are pairwise edge-disjoint.}
\end{center}

\section{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$.

\section{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:
\begin{itemize}
  \item the child-edges in $rootMask(e)$ become unavailable at $v$;
  \item 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;
  \item each endpoint contributes a full subtree state $dp[x][0]$.
\end{itemize}

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.

\section{Complexity}
Let $K \le 10$ be the maximum degree.
\begin{itemize}
  \item \textbf{States:} $O\!\left(\sum_v 2^{\deg(v)}\right)$.
  \item \textbf{Transitions:} $O(MN + M2^K)$, matching the official bound.
  \item \textbf{Space:} $O\!\left(\sum_v 2^{\deg(v)}\right)$.
\end{itemize}

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

\section{Implementation}
\begin{lstlisting}
// 1. Root the tree and compute LCA.
// 2. Ignore all non-tree edges whose tree path has odd length.
// 3. Group the remaining edges by LCA.
// 4. Process nodes bottom-up and fill dp[v][mask].
// 5. Answer = total_non_tree_weight - dp[root][0].
\end{lstlisting}

\end{document}