結果
問題 | No.2677 Minmax Independent Set |
ユーザー |
![]() |
提出日時 | 2024-03-15 23:34:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 487 ms / 2,000 ms |
コード長 | 2,563 bytes |
コンパイル時間 | 2,535 ms |
コンパイル使用メモリ | 205,932 KB |
最終ジャッジ日時 | 2025-02-20 06:10:35 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 61 |
ソースコード
#include <bits/stdc++.h> namespace zawa { using i16 = std::int16_t; using i32 = std::int32_t; using i64 = std::int64_t; using i128 = __int128_t; using u8 = std::uint8_t; using u16 = std::uint16_t; using u32 = std::uint32_t; using u64 = std::uint64_t; using usize = std::size_t; } // namespace zawa namespace zawa { void SetFastIO() { std::cin.tie(nullptr)->sync_with_stdio(false); } void SetPrecision(u32 dig) { std::cout << std::fixed << std::setprecision(dig); } } // namespace zawa using namespace zawa; int main() { SetFastIO(); int n; std::cin >> n; std::vector g(n, std::vector<int>{}); for (int _{} ; _ < n - 1 ; _++) { int u, v; std::cin >> u >> v; u--; v--; g[u].emplace_back(v); g[v].emplace_back(u); } std::vector dp(n, std::vector<int>(2)); auto dfs{[&](auto dfs, int v, int p) -> void { for (auto x : g[v]) if (x != p) dfs(dfs, x, v); for (auto x : g[v]) if (x != p) { dp[v][0] += std::max(dp[x][0], dp[x][1]); } dp[v][1] = 1; for (auto x : g[v]) if (x != p) { dp[v][1] += dp[x][0]; } return; }}; dfs(dfs, 0, -1); int ans{dp[0][1]}; auto dfs2{[&](auto dfs, int v, int p, std::vector<int> propa) -> void { // std::cout << v + 1 << " -> " << propa[0] << ' ' << propa[1] << std::endl; assert((int)propa.size() == 2); int is{1}; for (auto x : g[v]) is += (x == p ? propa[0] : dp[x][0]); ans = std::min(ans, is); int m{(int)g[v].size()}; std::vector a(m, std::vector<int>(2)); for (int i{} ; i < m ; i++) { a[i] = (g[v][i] == p ? propa : dp[g[v][i]]); } std::vector pref(m + 1, std::vector<int>(2)); std::vector suf(m + 1, std::vector<int>(2)); pref[0][1] = 0; for (int i{} ; i < m ; i++) { pref[i + 1][0] = pref[i][0] + std::max(a[i][0], a[i][1]); pref[i + 1][1] = pref[i][1] + a[i][0]; } suf[m][1] = 0; for (int i{m - 1} ; i >= 0 ; i--) { suf[i][0] = suf[i + 1][0] + std::max(a[i][0], a[i][1]); suf[i][1] = suf[i + 1][1] + a[i][0]; } for (int i{} ; i < m ; i++) { if (g[v][i] == p) continue; std::vector<int> next(2); next[0] = pref[i][0] + suf[i + 1][0]; next[1] = pref[i][1] + suf[i + 1][1] + 1; dfs(dfs, g[v][i], v, next); } }}; dfs2(dfs2, 0, -1, { 0, 0 }); std::cout << ans << '\n'; }