結果
問題 | No.2677 Minmax Independent Set |
ユーザー |
👑 ![]() |
提出日時 | 2024-03-13 22:34:56 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 758 ms / 2,000 ms |
コード長 | 4,465 bytes |
コンパイル時間 | 2,438 ms |
コンパイル使用メモリ | 220,264 KB |
実行使用メモリ | 121,984 KB |
最終ジャッジ日時 | 2024-09-30 00:16:38 |
合計ジャッジ時間 | 26,371 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 61 |
ソースコード
#include <bits/stdc++.h>using namespace std;// nu50218's library// 以下の形で計算する木DPを、すべての根について計算する。// dp[r] = f(r, op{ g(r, c, dp[c]) | c in children[r]})// ただし、以下を満たす。// - op は演算の順序に寄らない// - e() は op の単位元// - op(\emptyset) := e()// - op(x) := xtemplate <class S, S (*op)(S, S), S (*e)(), S (*f)(int, S), S (*g)(int, int, S)>struct ReRooting {ReRooting(int _n) : n(_n), adj(_n), dp(_n), gdp(_n), idx(_n), product_left(_n), product_right(_n) {}void add_edge(int u, int v) {assert(0 <= u && u < n);assert(0 <= v && v < n);adj[u].push_back(v);adj[v].push_back(u);}void calc() {calculated = true;if (n == 1) return;for (int i = 0; i < n; i++) {int cnt = 0;for (auto&& x : adj[i]) {idx[i][x] = cnt;cnt++;}dp[i].resize(cnt);gdp[i].resize(cnt);}rec(0);propagate(0);}S value(int r, int par = -1) {assert(calculated);assert(0 <= r && r < n);assert(par < n);if (n == 1) return f(r, e());if (idx[r].count(par) == 0) {return f(r, product_right[r].front());}const int i = idx[r][par];const int deg = adj[r].size();S prod_l = (i != 0 ? product_left[r][i - 1] : e());S prod_r = (i != deg - 1 ? product_right[r][i + 1] : e());return f(r, op(prod_l, prod_r));}private:int n;std::vector<std::vector<int>> adj;bool calculated = false;// dp[i][idx[j]] := iを削除して得られる連結成分のうちjを根とした木に対する木DPの結果std::vector<std::vector<S>> dp;// gdp[i][idx[j]] := g(i, j, dp[i][idx[j]])std::vector<std::vector<S>> gdp;std::vector<std::unordered_map<int, int>> idx;// product_{left/right} := (左/右)からのdp[i]の総積std::vector<std::vector<S>> product_left;std::vector<std::vector<S>> product_right;S rec(int r, int par = -1) {S prod = e();for (auto&& c : adj[r]) {if (c == par) continue;S val = rec(c, r);prod = op(prod, g(r, c, val));}S ret = f(r, prod);if (par != -1) {dp[par][idx[par][r]] = ret;gdp[par][idx[par][r]] = g(par, r, ret);}return ret;}void propagate(int r, int par = -1, S par_val = e()) {// fill dp[root]if (par != -1) {dp[r][idx[r][par]] = par_val;gdp[r][idx[r][par]] = g(r, par, par_val);}// construct product_{left/right}[root] from gdp[root]const int deg = adj[r].size();product_left[r].resize(deg);product_left[r][0] = gdp[r][0];product_right[r].resize(deg);product_right[r][deg - 1] = gdp[r][deg - 1];for (int i = 1; i < deg; i++) {product_left[r][i] = op(gdp[r][i], product_left[r][i - 1]);}for (int i = deg - 2; i >= 0; i--) {product_right[r][i] = op(gdp[r][i], product_right[r][i + 1]);}// propagatefor (auto&& c : adj[r]) {if (c == par) continue;propagate(c, r, value(r, c));}}};// dp[r][0] := r を黒く塗らなかったときの最大独立集合のサイズ// dp[r][1] := r を黒く塗ったときの最大独立集合のサイズ// 遷移は以下のとおり// dp[r][0] = \sum_{c \in children[r]} max(dp[c][0], dp[c][1])// dp[r][1] = 1 + \sum_{c \in children[r]} dp[c][0]using S = pair<int, int>;S op(S x, S y) {return {x.first + y.first, x.second + y.second};}S e() {return {0, 0};}S f([[maybe_unused]] int r, S x) {return {x.first, 1 + x.second};}S g([[maybe_unused]] int r, [[maybe_unused]] int c, S x) {return {max(x.first, x.second), x.first};}int main() {int N;cin >> N;ReRooting<S, op, e, f, g> rerooting(N);for (int i = 0; i < N - 1; i++) {int u, v;cin >> u >> v;u--;v--;rerooting.add_edge(u, v);}rerooting.calc();int ans = numeric_limits<int>::max();for (int i = 0; i < N; i++) {ans = min(ans, rerooting.value(i).second);}cout << ans << endl;}