結果
問題 | No.2677 Minmax Independent Set |
ユーザー |
|
提出日時 | 2024-03-15 23:03:24 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 240 ms / 2,000 ms |
コード長 | 3,193 bytes |
コンパイル時間 | 2,105 ms |
コンパイル使用メモリ | 213,236 KB |
実行使用メモリ | 73,520 KB |
最終ジャッジ日時 | 2024-09-30 02:38:05 |
合計ジャッジ時間 | 9,687 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 61 |
ソースコード
#include <bits/stdc++.h>using namespace std;template<class T> istream& operator >> (istream& is, vector<T>& vec) {for(T& x : vec) is >> x;return is;}template<class T> ostream& operator << (ostream& os, const vector<T>& vec) {if(vec.empty()) return os;os << vec[0];for(auto it = vec.begin(); ++it != vec.end(); ) os << ' ' << *it;return os;}struct ReRooting{using T = array<int, 2>;const T identity = T({0, 0}); //mergeの演算に対する単位元int n;vector<vector<int>> G;vector<vector<T>> dp;vector<T> ans;//vのi番目の辺の子からRを受け取ったときの処理T receive(int v, int i, T &R){return T(R);}//全体の累積lに子receiveの値をmerge//mergeの演算はモノイドでなくてはならないT merge(T l, T r){return T({l[0] + r[0], l[1] + r[1]});}//親に渡すときの処理T givep(int v, T cum){return T({max(cum[0], 1 + cum[1]), cum[0]});}ReRooting() {}ReRooting(int N):n(N){G.resize(N);dp.resize(N);ans.resize(N, identity);}void add_edge(int a, int b) {G[a].emplace_back(b);G[b].emplace_back(a);}void read(){int a, b;for(int i = 1; i < n; i++){cin >> a >> b;a--, b--;G[a].emplace_back(b);G[b].emplace_back(a);}}void build() {dfs(0); // 普通に木DPdfs2(0, identity); // 残りの部分木に対応するDPを計算}T dfs(int v, int p = -1) {T res = identity;int deg = G[v].size();dp[v] = vector<T>(deg, identity);for (int i = 0; i < deg; i++) {int u = G[v][i];if (u == p) continue;dp[v][i] = dfs(u, v);res = merge(res, receive(v, i, dp[v][i]) );}return givep(v,res);}void dfs2(int v, const T& dp_p, int p = -1) {int deg = G[v].size();for (int i = 0; i < deg; i++) { // 前のdfsで計算した有向辺に対応する部分木のDPを保存if (G[v][i] == p){dp[v][i] = dp_p; break;}}vector<T> dp_l(deg + 1, identity), dp_r(deg + 1, identity); // 累積mergefor (int i = 0; i < deg; i++) {dp_l[i + 1] = merge(dp_l[i], receive(v, i, dp[v][i]));}for (int i = deg - 1; i >= 0; i--) {dp_r[i] = merge(dp_r[i + 1], receive(v, i, dp[v][i]));}//ans[v] = dp_l[deg]; // 頂点 v の答えfor(int i = 0; i < deg; i++){ans[v][1] += dp[v][i][1];}ans[v][1]++;for (int i = 0; i < deg; i++) { // 一つ隣の頂点に対しても同様に計算int u = G[v][i];if (u == p) continue;dfs2(u, givep(v,merge(dp_l[i], dp_r[i + 1])),v);}}};int main(){ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n;ReRooting g(n);g.read();g.build();int ans = 1 << 30;for(int v = 0; v < n; v++) ans = min(ans, g.ans[v][1]);cout << ans << '\n';}