(Very Hard) IOI 2007 Day 2 Problem 3 - Training

IOI 2007 TRAINING

原题链接：https://oj.uz/problem/view/IOI07_training

官方题解：https://ioinformatics.org/files/ioi2007solutions.pdf

题目描述

有$N$个节点，$M$条边，其中$N-1$条边是“树边”，$N$个节点和这$N-1$条边能够组成一颗所有节点都连通的树，其它的边都是“非树边”，每一条“非树边$e$”都有一个相应的费用$w(e)$，这些“非树边”是可以删除的，删除边需要付出对应的费用；现在的任务目标是：删除某些“非树边”，使得剩下的图中，不存在边的数量为偶数的环，并且删除“非树边”所付出的费用和最小，求这个最小费用。

解决方案

参考：https://ioinformatics.org/files/ioi2007solutions.pdf
题目要我们求删除一些“非树边”使得不存在边数为偶数的环时删除的边的最小费用，我们把边数为偶数的环称为“偶环”。我们可以逆向思维思考：从一棵树开始，我们需要寻找一个总费用最大的“非树边”集合，将这些“非树边”添加到这棵树上不会形成任何“偶环”，这和题目要求的是同一个问题。

一些观察结果

“奇边”和“偶边”

考虑一条“非树边” $e=\{A,B\}$，我们定义边$e$的“树路径”为连接$A$与$B$，所有的边都是“树边”的那条唯一的路径，我们用$TP(e)$来表示边$e$的“树路径”，如果$TP(e)$上边的数量为偶数，我们称$e$为“偶边”，否则为“奇边”。很明显，任意“奇边”和这条奇边对应的“树路径”会组成一个“偶环”，因此，所有的“奇边”都不能够添加到我们的图上，我们可以完全忽略这些“奇边“。

两条“偶边”之间的关系

单独的“偶边”是可能存在于图上的，然而，如果我们包含了多条“偶边”，就有可能形成“偶环”，举个例子：如果$e1$和$e2$是“偶边”，且$TP(e1)$和$TP(e2)$有一些公共的“树边”，则将$e1$和$e2$同时添加到图中必定会形成“偶环”。

简单描述一下证明： 首先公共的“树边”必定是连续的，因为“树边”在树上，不存在环；设$e1$和$TP(e1)$组成的是“奇环1”，$e2$和$TP(e2)$组成的是“奇环2”，假设“奇环1”的边数为$L1$，“奇环2”的边数为$L2$，公共边的长度为$L_c$，设“奇环1”和“奇环2”去掉公共“树边”后的路径分别为$P1$和$P2$，$P1$和$P2$拥有相同的端点，即公共“树边”的两个端点，因此$P1$和$P2$可以组成一个新的环，新的环长度为$L1+L2-2*L_c$，且$L1$、$L2$均为奇数，因此$L1+L2-2*L_c$必定为偶数，即$P1$和$P2$组成了一个新的偶环。

根据上述论断，我们可以得出结论：每条“树边”最多只能被一个“奇环”包含。也就是说，我们在添加“偶边”到图中的时候，保证每条“树边”最多只被一个“奇环”包含，就不会形成任何“偶环”

参考解决方案

现在可以使用观察结果来开发出一个动态规划的解决方案，用state表示一颗给定子树的状态，对于每个状态，我们计算出满足条件每条“树边”最多只被一个“奇环”包含时，能够被添加到这颗子树上的总费用最大的“偶边”集合的总费用，最终答案就是初始树对应的state。

为了能够递归地进行处理，我们考虑所有“树路径”经过根节点的“偶边”，对于这颗子树，我们有两个选择：

1. 不添加任何“树路径”经过根节点的“偶边”，这种情况下，我们直接删掉根节点，然后对删掉根节点后的每一棵子树计算最优方案。
2. 我们选择某条“树路径”经过根节点的“偶边”$e$，然后，我们删除所有“树路径”$TP(e)$上的“树边”（因为它们已经被包含在一个“奇环”中了，不能够再被包含在其他的“奇环”中了），然后，我们继续对这些边被删除后产生的每一颗子树计算最优方案，并添加$w(e)$到最终的最优方案中。

让我们用下图所示的树来作为例子：

1. 不添加任何“树路径”经过根节点的“偶边”
   
2. 选择某条“树路径”经过根节点的“偶边”$e$
   

时间复杂度

$O(mn+nlogn+mlogn+m·2^k)$

代码

#include <bits/stdc++.h>

using namespace std;

template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &pa) { is >> pa.first >> pa.second; return is; }
template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << "(" << pa.first << "," << pa.second << ")"; return os; }
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename T> void resize_array(vector<T> &vec, int len) { vec.resize(len); }
template <typename T, typename... Args> void resize_array(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) resize_array(v, args...); }
template <typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template <typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }

template <unsigned int MOD>
class ModInt {
 public:
  // static unsigned int MOD;
  ModInt(unsigned long long _v = 0) { set_v((_v % MOD + MOD)); }
  explicit operator bool() const { return val != 0; }
  ModInt operator-() const { return ModInt() - *this; }
  ModInt operator+(const ModInt &r) const {
    return ModInt().set_v(val + r.val);
  }
  ModInt operator-(const ModInt &r) const {
    return ModInt().set_v(val + MOD - r.val);
  }
  ModInt operator*(const ModInt &r) const {
    return ModInt().set_v(
        (unsigned int)((unsigned long long)(val)*r.val % MOD));
  }
  ModInt operator/(const ModInt &r) const { return *this * r.inv(); }
  ModInt &operator+=(const ModInt &r) { return *this = *this + r; }
  ModInt &operator-=(const ModInt &r) { return *this = *this - r; }
  ModInt &operator*=(const ModInt &r) { return *this = *this * r; }
  ModInt &operator/=(const ModInt &r) { return *this = *this / r; }
  // ModInt &operator=(unsigned long long _v) { set_v((_v % MOD + MOD)); return
  // *this; }
  unsigned int operator=(unsigned long long _v) {
    set_v((_v % MOD + MOD));
    return val;
  }
  bool operator==(const ModInt &r) const { return val == r.val; }
  bool operator!=(const ModInt &r) const { return val != r.val; }
  ModInt pow(long long n) const {
    ModInt x = *this, r = 1;
    while (n) {
      if (n & 1) r *= x;
      x *= x;
      n >>= 1;
    }
    return r;
  }
  ModInt inv() const { return pow(MOD - 2); }
  unsigned int get_val() { return val; }
  friend ostream &operator<<(ostream &os, const ModInt &r) {
    return os << r.val;
  }
  friend istream &operator>>(istream &is, ModInt &r) { return is >> r.val; }

 private:
  unsigned int val;
  ModInt &set_v(unsigned int _v) {
    val = (_v < MOD) ? _v : _v - MOD;
    return *this;
  }
};
constexpr unsigned int mod = 1e9 + 7;
using Mint = ModInt<mod>;

#define rep(i, a, n) for (int i = a; i < (n); i++)
#define per(i, a, n) for (int i = (n)-1; i >= a; i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef vector<int> vi;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef double db;
#if DEBUG
#define dbg(x) \
  cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;
#else
#define dbg(x)
#endif

// template<typename T>
class Tree { // 下标从0开始
  struct LCA {
    int node;
    int son1 = -1, son2 = -1;
    int dist = 0;
    friend ostream &operator<<(ostream &os, const LCA &r) {
      return os << r.node << "(" << r.son1 << ", " << r.son2 << ")";
    }
  };
 public:
  Tree(int node_num, int root) {
    edges.resize(node_num);
    size.resize(node_num);
    weight.resize(node_num);
    nth_son.resize(node_num);
    centroid[0].resize(node_num, -1);
    centroid[1].resize(node_num, -1);
    this->root = root;

    int bit_num = 1;
    while ((1 << bit_num) < node_num) bit_num++;
    parent.resize(node_num, vi(bit_num));
  }
  void AddEdge(int u, int v) {
    edges[u].emplace_back(v);
    edges[v].emplace_back(u);
  }
  void Dfs() {
    function<void(int, int)> dfs = [&](int u, int p) {
      size[u] = 1;
      for (int i = 0; i < int(edges[u].size()); ++i) {
        int v = edges[u][i];
        if (v != p) {
          parent[v][0] = u;
          nth_son[v] = i;
          dfs(v, u);
          size[u] += size[v];
          weight[u] = max(weight[u], size[v]);
        }
      }

      centroid[0][u] = u;
      for (int v : edges[u]) {
        if (v == p) continue;
        int cen = centroid[0][v];
        while (cen != u) {
          if (max(weight[cen], size[u] - size[cen]) <= size[u] / 2) {
            centroid[0][u] = cen;
            int fa_cen = parent[cen][0];
            if (max(weight[fa_cen], size[u] - size[fa_cen]) <= size[u] / 2)
              centroid[1][u] = fa_cen;
            break;
          }
          else {
            cen = parent[cen][0];
          }
        }
      }
    };
    parent[root][0] = -1;
    nth_son[root] = -1;
    dfs(root, -1);
    // O(nlogn)
    for (int d = 1; d < int(parent[0].size()); ++d) {
      for (int u = 0; u < int(parent.size()); ++u) {
        if (parent[u][d - 1] == -1)
          parent[u][d] = -1;
        else
          parent[u][d] = parent[parent[u][d - 1]][d - 1];
      }
    }
  }

  int GetDepth(int idx) {
    int depth = 0;
    int d = sz(parent[0]) - 1;
    while (idx != root) {
      if (parent[idx][d] != -1) {
        depth |= (1 << d);
        idx = parent[idx][d];
      }
      d--;
    }
    return depth;
  };

  // least common ancestor
  LCA GetLca(int u, int v) {
    int d1 = GetDepth(u);
    int d2 = GetDepth(v);

    if (d1 < d2) {
      swap(u, v);
    }
    LCA lca;
    int t = abs(d1 - d2);
    if (t > 0) {
      t--;
      rep(i, 0, sz(parent[0])) {
        if (t & (1 << i)) u = parent[u][i];
      }
      lca.son1 = nth_son[u];
      u = parent[u][0];
    }
    if (u == v) {
      lca.node = u;
      lca.dist = abs(d1 - d2);
      return lca;
    }

    int d = sz(parent[0]) - 1;
    while (d >= 0) {
      if (parent[u][d] != parent[v][d]) {
        u = parent[u][d];
        v = parent[v][d];
      }
      d--;
    }
    lca.son1 = nth_son[u];
    lca.son2 = nth_son[v];
    lca.node = parent[u][0];
    lca.dist = d1 + d2 - 2 * GetDepth(lca.node);
    return lca;
  }

  const vector<int>& GetCentroid(int idx) {
    return centroid[idx];
  }

  const vector<vector<int>>& GetEdges() {
    return edges;
  }

  const vector<vector<int>>& GetParent() {
    return parent;
  }

  const vector<int>& GetNthSon() {
    return nth_son;
  }

 private:
  // nth_son[i] indicates which son of the father is i.
  // nth_son[i] 表示i是父节点的第几个子节点
  vector<int> nth_son;
  vector<vector<int>> edges;
  vector<vector<int>> parent;
  vector<int> size; // size[i]表示以节点i为根的子树（整颗数以root为根）的节点个数，包括i节点本身
  vector<int> weight;  // weight[i]表示节点i的所有子树的节点数的最大值，包括向上的子树
  vector<int> centroid[2]; //centroid[i]表示以节点i为根的子树（整颗数以root为根）的重心，重心最多有两个（质心）
  int root = 0;
};

class Solution {
  struct Edge {
    int u, v;
    int cost;
    friend ostream &operator<<(ostream &os, const Edge &r) {
      return os << r.u << "-->" << r.v << ":" << r.cost;
    }
  };

 public:
  void Solve() {
    int n, m;
    // n<=1000, m<=5000
    while (cin >> n >> m) {
      int total_cost = 0;

      vi degree(n);
      Tree tree(n, 0);
      vector<Edge> edges;
      int u, v, c;
      rep(i, 0, m) {
        cin >> u >> v >> c;
        u--;
        v--;

        degree[u]++;
        degree[v]++;
        if (c == 0) {
          tree.AddEdge(u, v);
        } else {
          edges.emplace_back(Edge{u, v, c});
          total_cost += c;
        }
      }

      tree.Dfs();

      int max_degree = 1;
      rep(i, 0, n) max_degree = *max_element(all(degree));

      vector<Edge> even_edges;
      for (auto edge : edges) {
        // if (tree_path_len[edge.u][edge.v] % 2 == 0) {
        if (tree.GetLca(edge.u, edge.v).dist % 2 == 0) {
          even_edges.emplace_back(edge);
        }
      }

      // O(mlogn)
      vector<vi> node_to_even_edges(n);
      vector<vector<pii>> node_to_direct_sons(n);
      rep(i, 0, sz(even_edges)) {
        // dbg(mp(even_edges[i].u, even_edges[i].v));
        auto lca = tree.GetLca(even_edges[i].u, even_edges[i].v);
        // dbg(lca);
        node_to_even_edges[lca.node].emplace_back(i);
        node_to_direct_sons[lca.node].emplace_back(mp(lca.son1, lca.son2));
      }

      // O(m*2^k)
      vector<vi> dp(n, vi(1 << max_degree, -1));
      vector<vi> cache(n, vi(n, -1));
      const vector<vector<int>>& tree_edges = tree.GetEdges();
      rep(i, 0, n) cache[i][i] = 0;
      rep(u, 0, n) {
        for (int v : tree_edges[u]) {
          cache[u][v] = cache[v][u] = 0;
        }
      }
      const vector<vi>& parent = tree.GetParent();
      function<int(int, int)> get_most_cost = [&](int node, int mask) {
        // dbg(mp(node, mask));
        if (dp[node][mask] != -1) return dp[node][mask];
        int cost = 0;
        rep(i, 0, sz(tree_edges[node])) {
          if ((1 << i) & mask) continue;
          if (tree_edges[node][i] == parent[node][0]) continue;
          cost += get_most_cost(tree_edges[node][i], 0);
        }
        dp[node][mask] = max(dp[node][mask], cost);

        const vector<int>& nth_son = tree.GetNthSon();
        rep(idx, 0, sz(node_to_even_edges[node])) {
          int i = node_to_even_edges[node][idx];
          if (node_to_direct_sons[node][idx].first != -1 &&
              (mask & (1 << node_to_direct_sons[node][idx].first)))
            continue;
          if (node_to_direct_sons[node][idx].second != -1 &&
              (mask & (1 << node_to_direct_sons[node][idx].second)))
            continue;

          cost = even_edges[i].cost;
          int u = even_edges[i].u, v = even_edges[i].v;
          if (u != node) cost += get_most_cost(u, 0);
          if (v != node) cost += get_most_cost(v, 0);

          vi nodes, subtree_cost;
          while (true) {
            if (cache[node][u] != -1) {
              if (sz(nodes) > 0) {
                cache[node][nodes.back()] =
                    subtree_cost.back() + cache[node][u];
                per(i, 0, sz(nodes) - 1) {
                  cache[node][nodes[i]] =
                      subtree_cost[i] + cache[node][nodes[i + 1]];
                }
              }
              break;
            }
            int p = parent[u][0];
            nodes.emplace_back(u);
            subtree_cost.emplace_back(get_most_cost(p, (1 << nth_son[u])));
            u = p;
          }
          cost += cache[node][even_edges[i].u];

          nodes.clear(), subtree_cost.clear();
          while (true) {
            if (cache[node][v] != -1) {
              if (sz(nodes) > 0) {
                cache[node][nodes.back()] =
                    subtree_cost.back() + cache[node][v];
                per(i, 0, sz(nodes) - 1) {
                  cache[node][nodes[i]] =
                      subtree_cost[i] + cache[node][nodes[i + 1]];
                }
              }
              break;
            }
            int p = parent[v][0];
            nodes.emplace_back(v);
            subtree_cost.emplace_back(get_most_cost(p, (1 << nth_son[v])));
            v = p;
          }
          cost += cache[node][even_edges[i].v];

          int mask2 = mask;
          if (node_to_direct_sons[node][idx].first != -1)
            mask2 |= (1 << node_to_direct_sons[node][idx].first);
          if (node_to_direct_sons[node][idx].second != -1)
            mask2 |= (1 << node_to_direct_sons[node][idx].second);
          cost += get_most_cost(node, mask2);
          dp[node][mask] = max(dp[node][mask], cost);
        }

        return dp[node][mask];
      };

      cout << total_cost - get_most_cost(0, 0) << endl;
    }
  }

 private:
};

// #define USACO 1
void set_io(const string &name = "") {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
#if FILE_IO || USACO
  if (!name.empty()) {
    freopen((name + ".in").c_str(), "r", stdin);
    freopen((name + ".out").c_str(), "w", stdout);
  }
#endif
}

int main() {
#if USACO
  set_io("time");
#else
  set_io("input");
#endif
  Solution().Solve();

  return 0;
}