結果

問題 No.2677 Minmax Independent Set
ユーザー 👑 eoeoeoeo
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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) := x
template <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]] := ijDP
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]);
}
// propagate
for (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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0