#1164586 (C++23) No.2677 Minmax Independent Set

• 問題: No.2677 Minmax Independent Set
• ユーザー: iastm
• 提出日時: 2026-05-13 17:24:35
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 229 ms / 2,000 ms
• コード長: 9,273 bytes
• コンパイル時間: 1,626 ms
• コンパイル使用メモリ: 188,400 KB
• 実行使用メモリ: 79,904 KB
• 最終ジャッジ日時: 2026-05-13 17:24:48
• 合計ジャッジ時間: 12,441 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_1

ファイルパターン	結果
sample	AC * 3
other	AC * 61

ソースコード

#include <iostream>
#include <vector>
#include <array>
// #include <kotone/rerooting>
// https://github.com/amiast/cpp-utility

#ifndef KOTONE_REROOTING_HPP
#define KOTONE_REROOTING_HPP 1

#include <vector>
#include <cassert>
// #include <kotone/dsu>
// https://github.com/amiast/cpp-utility

#ifndef KOTONE_DSU_HPP
#define KOTONE_DSU_HPP 1

#include <vector>
#include <cassert>
#include <algorithm>

namespace kotone {

// A basic data structure that monitors connectivity in a graph.
// Optionally monitors the potential differences between nodes.
// Reference: AtCoder Library
template <typename T = int> struct dsu {
  protected:
    int _num_nodes;
    bool _defines_pd = true;
    std::vector<int> _parent_or_size;
    std::vector<T> _p;

    T _potential(int v) {
        leader(v);
        return _p[v];
    }

  public:
    dsu() : _num_nodes(0) {}

    // Creates a graph with the specified `num_nodes` and no edges.
    dsu(int num_nodes) : _num_nodes(num_nodes), _parent_or_size(num_nodes, -1), _p(num_nodes) {
        assert(num_nodes >= 0);
        assert(num_nodes <= 100000000);
    }

    // Returns the leader of the connected component containing `v`.
    int leader(int v) {
        assert(v >= 0);
        assert(v < _num_nodes);
        if (_parent_or_size[v] < 0) return v;
        int l = leader(_parent_or_size[v]);
        _p[v] = _p[v] + _p[_parent_or_size[v]];
        return _parent_or_size[v] = l;
    }

    // Returns whether `u` and `v` belong to the same connected component.
    bool connected(int u, int v) {
        return leader(u) == leader(v);
    }

    // Returns the potential difference from `u` to `v`.
    // Requires `u` and `v` to be connected.
    // Requires all previous `merge()` calls to define potential differences.
    T potential_diff(int u, int v) {
        assert(connected(u, v));
        assert(_defines_pd);
        return _potential(v) - _potential(u);
    };

    // Adds an edge between `u` and `v`,
    // then returns the leader of the merged component.
    virtual int merge(int u, int v) {
        _defines_pd = false;
        return merge(u, v, T{});
    }

    // Adds an edge between `u` and `v`,
    // then returns the leader of the merged component.
    // If `u` and `v` are not formerly connected,
    // defines the potential difference from `u` to `v` as `pd`.
    virtual int merge(int u, int v, T pd) {
        if (connected(u, v)) return leader(u);
        pd = pd + _potential(u) - _potential(v);
        u = leader(u);
        v = leader(v);
        if (_parent_or_size[u] > _parent_or_size[v]) {
            std::swap(u, v);
            pd = -pd;
        }
        _parent_or_size[u] += _parent_or_size[v];
        _parent_or_size[v] = u;
        _p[v] = pd;
        return u;
    }

    // Returns the size of the connected component containing `v`.
    int size(int v) {
        return -_parent_or_size[leader(v)];
    }

    // Returns a vector of connected components as vectors of node indices.
    // The order of components is undefined.
    // Node indices in each group's vector appear in ascending order.
    std::vector<std::vector<int>> components() {
        std::vector<std::vector<int>> temp(_num_nodes), result;
        for (int i = 0; i < _num_nodes; i++) temp[leader(i)].emplace_back(i);
        for (int i = 0; i < _num_nodes; i++) {
            if (temp[i].size()) {
                result.push_back(std::move(temp[i]));
            }
        }
        return result;
    }
};

// An extended DSU with internal mapping between connected components and a semigroup.
// Optionally monitors the potential differences between nodes.
template <typename S, S (*op)(S, S), typename T = int> struct extended_dsu : dsu<T> {
  protected:
    std::vector<S> _map;

  public:
    extended_dsu() : dsu<T>() {}

    // Creates a graph with the specified `num_nodes` and no edges.
    // Each connected component is mapped to a value-initialized instance of `S`.
    extended_dsu(int num_nodes) : dsu<T>(num_nodes), _map(num_nodes) {}

    // Creates a graph with the specified `num_nodes` and no edges.
    // Each connected component is mapped to a copy of `init_x`.
    extended_dsu(int num_nodes, S init_x) : dsu<T>(num_nodes), _map(num_nodes, init_x) {}

    // Creates a graph with no edges.
    // For all `v`, maps connected component containing `v` to `vec[v]`.
    extended_dsu(const std::vector<S> &vec) : dsu<T>(vec.size()), _map(vec) {}

    // Adds an edge between `u` and `v`,
    // then returns the leader of the merged component.
    // Also merges their images under the mapping.
    int merge(int u, int v) override {
        this->_defines_pd = false;
        return merge(u, v, T{});
    }

    // Adds an edge between `u` and `v`,
    // then returns the leader of the merged component.
    // Also merges their images under the mapping.
    // If `u` and `v` are not formerly connected,
    // defines the potential difference from `u` to `v` as `pd`.
    int merge(int u, int v, T pd) override {
        if (this->connected(u, v)) return this->leader(u);
        S result = op(_map[this->leader(u)], _map[this->leader(v)]);
        _map[dsu<T>::merge(u, v, pd)] = std::move(result);
        return this->leader(u);
    }

    // Returns a copy of the image mapped from the connected component containing `v`.
    S get(int v) {
        return _map[this->leader(v)];
    }

    // Reassigns `x` as the image mapped from the connected component containing `v`,
    // then returns the leader of the modified component.
    int set(int v, S x) {
        v = this->leader(v);
        _map[v] = std::move(x);
        return v;
    }
};

}  // namespace kotone

#endif  // KOTONE_DSU_HPP

namespace kotone {

// Maintains dynamic programming for commutative monoids at different roots of trees in a forest.
// Requires the following functions:
// - `S merge(S dp_l, S dp_r)`
// - `S apply(S dp_child, int child, int parent)`
// - `S identity()`
template <typename S, S (*merge)(S, S), S (*apply)(S, int, int), S (*identity)()> struct rerooting {
  private:
    int _size = 0;
    std::vector<std::vector<int>> _tree;
    std::vector<S> _dp;
    kotone::dsu<int> _dsu;

    void _dfs_forward(int u, int p) {
        _dp[u] = identity();
        for (int v : _tree[u]) {
            if (v == p) continue;
            _dfs_forward(v, u);
            _dp[u] = merge(_dp[u], apply(_dp[v], v, u));
        }
    }

    void _dfs_reverse(int u, int p, S parent_acc, std::vector<S> &result) {
        int deg = static_cast<int>(_tree[u].size());
        std::vector<S> prefix(deg + 1, identity()), suffix(deg + 1, identity());
        for (int i = 0; i < deg; i++) {
            int v = _tree[u][i];
            if (v == p) prefix[i + 1] = merge(prefix[i], apply(parent_acc, p, u));
            else prefix[i + 1] = merge(prefix[i], apply(_dp[v], v, u));
        }
        for (int i = deg - 1; i >= 0; i--) {
            int v = _tree[u][i];
            if (v == p) suffix[i] = merge(suffix[i + 1], apply(parent_acc, p, u));
            else suffix[i] = merge(suffix[i + 1], apply(_dp[v], v, u));
        }
        result[u] = prefix[deg];
        for (int i = 0; i < deg; i++) {
            int v = _tree[u][i];
            if (v == p) continue;
            S acc = merge(prefix[i], suffix[i + 1]);
            _dfs_reverse(v, u, acc, result);
        }
    }

  public:
    rerooting() {}

    // Constructs a forest with the specified number of disconnected nodes.
    // Requires `0 <= num_nodes <= 100000000`.
    rerooting(int num_nodes) : _size(num_nodes), _dsu(num_nodes) {
        assert(0 <= num_nodes && num_nodes <= 100000000);
        _tree.resize(num_nodes);
        _dp.resize(num_nodes);
    }

    // Returns the number of nodes in the forest.
    int size() const {
        return _size;
    }

    // Adds an edge between nodes `u` and `v`.
    // Requires `0 <= u, v < size()`.
    // Requires `u` and `v` to be formerly disconnected.
    void add_edge(int u, int v) {
        assert(0 <= u && u < _size);
        assert(0 <= v && v < _size);
        assert(!_dsu.connected(u, v));
        _tree[u].push_back(v);
        _tree[v].push_back(u);
        _dsu.merge(u, v);
    }

    // Evaluates and returns a vector of the function at different roots of trees in the forest.
    std::vector<S> evaluate() {
        std::vector<S> result(_size);
        for (int i = 0; i < _size; i++) {
            if (i != _dsu.leader(i)) continue;
            _dfs_forward(i, -1);
            _dfs_reverse(i, -1, identity(), result);
        }
        return result;
    }
};

}  // namespace kotone

#endif  // KOTONE_REROOTING_HPP

using S = std::array<int, 3>;

S merge(S a, S b) {
    return {std::max(a[0] + b[2], a[2] + b[0]), a[1] + b[1], a[2] + b[2]};
}

S apply(S x, int, int) {
    return {x[1] + 1, std::max(x[0], x[1]), x[1]};
}

S identity() {
    return {1, 0, 0};
}

int main() {
    int N;
    std::cin >> N;
    kotone::rerooting<S, merge, apply, identity> tree(N);
    for (int i = 1; i < N; i++) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;
        tree.add_edge(u, v);
    }

    int result = N;
    for (auto &arr : tree.evaluate()) {
        result = std::min(result, arr[0]);
    }
    std::cout << result << std::endl;
}