結果
問題 |
No.3189 Semifinal Stage
|
ユーザー |
![]() |
提出日時 | 2025-08-06 05:35:08 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 14,175 bytes |
コンパイル時間 | 2,230 ms |
コンパイル使用メモリ | 184,384 KB |
実行使用メモリ | 37,916 KB |
最終ジャッジ日時 | 2025-08-06 05:35:25 |
合計ジャッジ時間 | 13,527 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | WA * 30 |
ソースコード
#include <iostream> #include <iomanip> #include <cassert> #include <vector> #include <algorithm> #include <utility> #include <numeric> #include <tuple> #include <ranges> namespace ranges = std::ranges; namespace views = std::views; // #include "Src/Number/IntegerDivision.hpp" // #include "Src/Utility/BinarySearch.hpp" // #include "Src/Sequence/CompressedSequence.hpp" // #include "Src/Sequence/RunLengthEncoding.hpp" // #include "Src/Algebra/Group/AdditiveGroup.hpp" // #include "Src/DataStructure/FenwickTree/FenwickTree.hpp" #include <cstdint> #include <cstddef> 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 #include <concepts> namespace zawa { namespace concepts { template <class T> concept Semigroup = requires { typename T::Element; { T::operation(std::declval<typename T::Element>(), std::declval<typename T::Element>()) } -> std::same_as<typename T::Element>; }; } // namespace concepts } // namespace zawa namespace zawa { namespace concepts { template <class T> concept Identitiable = requires { typename T::Element; { T::identity() } -> std::same_as<typename T::Element>; }; template <class T> concept Monoid = Semigroup<T> and Identitiable<T>; } // namespace } // namespace zawa #include <functional> #include <type_traits> #include <ostream> namespace zawa { template <concepts::Monoid Monoid> class SegmentTree { public: using VM = Monoid; using V = typename VM::Element; using OM = Monoid; using O = typename OM::Element; SegmentTree() = default; explicit SegmentTree(usize n) : m_n{ n }, m_dat(n << 1, VM::identity()) {} explicit SegmentTree(const std::vector<V>& dat) : m_n{ dat.size() }, m_dat(dat.size() << 1, VM::identity()) { for (usize i{} ; i < m_n ; i++) { m_dat[i + m_n] = dat[i]; } for (usize i{m_n} ; i-- ; ) { m_dat[i] = VM::operation(m_dat[left(i)], m_dat[right(i)]); } } [[nodiscard]] inline usize size() const noexcept { return m_n; } [[nodiscard]] V get(usize i) const { assert(i < size()); return m_dat[i + m_n]; } [[nodiscard]] V operator[](usize i) const { assert(i < size()); return m_dat[i + m_n]; } void operation(usize i, const O& value) { assert(i < size()); i += size(); m_dat[i] = OM::operation(m_dat[i], value); while (i = parent(i), i) { m_dat[i] = VM::operation(m_dat[left(i)], m_dat[right(i)]); } } void assign(usize i, const V& value) { assert(i < size()); i += size(); m_dat[i] = value; while (i = parent(i), i) { m_dat[i] = VM::operation(m_dat[left(i)], m_dat[right(i)]); } } [[nodiscard]] V product(u32 l, u32 r) const { assert(l <= r and r <= size()); V L{ VM::identity() }, R{ VM::identity() }; for (l += size(), r += size() ; l < r ; l = parent(l), r = parent(r)) { if (l & 1) { L = VM::operation(L, m_dat[l++]); } if (r & 1) { R = VM::operation(m_dat[--r], R); } } return VM::operation(L, R); } template <class F> requires std::predicate<F, V> [[nodiscard]] usize maxRight(usize l, const F& f) { assert(l < size()); static_assert(std::is_convertible_v<decltype(f), std::function<bool(V)>>, "maxRight's argument f must be function bool(T)"); assert(f(VM::identity())); usize res{l}, width{1}; V prod{ VM::identity() }; // 現在の見ている頂点の幅をwidthで持つ // 境界がある頂点を含む部分木の根を探す // (折り返す時は必要以上の幅を持つ根になるが、widthを持っているのでオーバーしない) for (l += size() ; res + width <= size() ; l = parent(l), width <<= 1) if (l & 1) { if (not f(VM::operation(prod, m_dat[l]))) break; res += width; prod = VM::operation(prod, m_dat[l++]); } // 根から下って、境界を発見する while (l = left(l), width >>= 1) { if (res + width <= size() and f(VM::operation(prod, m_dat[l]))) { res += width; prod = VM::operation(prod, m_dat[l++]); } } return res; } template <class F> requires std::predicate<F, V> [[nodiscard]] usize minLeft(usize r, const F& f) const { assert(r <= size()); static_assert(std::is_convertible_v<decltype(f), std::function<bool(V)>>, "minLeft's argument f must be function bool(T)"); assert(f(VM::identity())); usize res{r}, width{1}; V prod{ VM::identity() }; for (r += size() ; res >= width ; r = parent(r), width <<= 1) if (r & 1) { if (not f(VM::operation(m_dat[r - 1], prod))) break; res -= width; prod = VM::operation(prod, m_dat[--r]); } while (r = left(r), width >>= 1) { if (res >= width and f(VM::operation(m_dat[r - 1], prod))) { res -= width; prod = VM::operation(m_dat[--r], prod); } } return res; } friend std::ostream& operator<<(std::ostream& os, const SegmentTree& st) { for (usize i{1} ; i < 2 * st.size() ; i++) { os << st.m_dat[i] << (i + 1 == 2 * st.size() ? "" : " "); } return os; } private: constexpr u32 left(u32 v) const { return v << 1; } constexpr u32 right(u32 v) const { return v << 1 | 1; } constexpr u32 parent(u32 v) const { return v >> 1; } usize m_n; std::vector<V> m_dat; }; } // namespace zawa // #include "Src/DataStructure/DisjointSetUnion/DisjointSetUnion.hpp" #include <cmath> #include <limits> namespace zawa { template <class V> class HeavyLightDecomposition { public: static constexpr V Invalid() noexcept { return INVALID; } HeavyLightDecomposition() = default; HeavyLightDecomposition(std::vector<std::vector<V>> T, V root = 0u) : n_{T.size()}, par_(n_), top_(n_), idx_(n_), inv_(n_), size_(n_, usize{1}), dep_(n_) { auto dfs1{[&](auto dfs, V v, V p, usize d) -> usize { par_[v] = p; dep_[v] = d; if (p != INVALID) { for (u32 i{} ; i + 1 < T[v].size() ; i++) if (T[v][i] == p) { std::swap(T[v][i], T[v].back()); break; } assert(T[v].back() == p); T[v].pop_back(); } for (V x : T[v]) { size_[v] += dfs(dfs, x, v, d + 1); } for (u32 i{1} ; i < T[v].size() ; i++) if (size_[T[v][0]] < size_[T[v][i]]) { std::swap(T[v][0], T[v][i]); } return size_[v]; }}; auto dfs2{[&](auto dfs, V v, V idx, V top) -> V { idx_[v] = idx++; inv_[idx_[v]] = v; top_[v] = top; if (T[v].size()) { idx = dfs(dfs, T[v][0], idx, top); for (u32 i{1} ; i < T[v].size() ; i++) { idx = dfs(dfs, T[v][i], idx, T[v][i]); } } return idx; }}; dfs1(dfs1, root, INVALID, 0u); dfs2(dfs2, root, 0u, root); } inline usize size() const noexcept { return n_; } usize size(V v) const noexcept { assert(v < (V)size()); return size_[v]; } usize depth(V v) const noexcept { assert(v < (V)size()); return dep_[v]; } usize top(V v) const noexcept { assert(v < (V)size()); return top_[v]; } V parent(V v) const noexcept { assert(v < (V)size()); return par_[v]; } V index(V v) const noexcept { assert(v < (V)size()); return idx_[v]; } V operator[](V v) const noexcept { assert(v < (V)size()); return idx_[v]; } std::vector<std::pair<V, V>> decomp(V s, V t) const { assert(s < (V)size()); assert(t < (V)size()); std::vector<std::pair<V, V>> res, ser; while (top_[s] != top_[t]) { if (dep_[top_[s]] >= dep_[top_[t]]) { res.emplace_back(s, top_[s]); s = top_[s]; if (par_[s] != INVALID) s = par_[s]; } else { ser.emplace_back(top_[t], t); t = top_[t]; if (par_[t] != INVALID) t = par_[t]; } } res.emplace_back(s, t); std::reverse(ser.begin(), ser.end()); res.insert(res.end(), ser.begin(), ser.end()); return res; } std::vector<std::pair<V, V>> operator()(V s, V t) const { return decomp(s, t); } V lca(V u, V v) const { assert(u < (V)size()); assert(v < (V)size()); while (top_[u] != top_[v]) { if (dep_[top_[u]] >= dep_[top_[v]]) { u = top_[u]; if (par_[u] != INVALID) u = par_[u]; } else { v = top_[v]; if (par_[v] != INVALID) v = par_[v]; } } return (dep_[u] <= dep_[v] ? u : v); } // pはvの祖先か? bool isAncestor(V v, V p) { assert(v < size()); assert(p < size()); if (dep_[v] < dep_[p]) return false; while (v != INVALID and top_[v] != top_[p]) { v = par_[top_[v]]; } return v != INVALID; } V levelAncestor(V v, usize step) const { assert(v < (V)size()); if (step > dep_[v]) return INVALID; while (true) { usize dist{dep_[v] - dep_[top_[v]]}; if (dist >= step) break; step -= dist + 1; v = par_[top_[v]]; } step = (dep_[v] - dep_[top_[v]]) - step; return inv_[idx_[top_[v]] + step]; } V jump(V s, V t, usize step) const { assert(s < (V)size()); assert(t < (V)size()); V uu{INVALID}, vv{INVALID}; usize d{}; for (auto [u, v] : decomp(s, t)) { usize dist{std::max(dep_[u], dep_[v]) - std::min(dep_[u], dep_[v])}; if (dist >= step) { uu = u; vv = v; d = dist; break; } step -= dist + 1; } if (uu == INVALID) return INVALID; if (dep_[uu] <= dep_[vv]) { return inv_[idx_[uu] + step]; } else { return inv_[idx_[vv] + (d - step)]; } } usize distance(V s, V t) const { assert(s < (V)size()); assert(t < (V)size()); usize res{}; for (auto [u, v] : decomp(s, t)) { if (dep_[u] > dep_[v]) std::swap(u, v); res += dep_[v] - dep_[u]; } return res; } private: static constexpr V INVALID{static_cast<V>(-1)}; usize n_{}; std::vector<V> par_{}, top_{}, idx_{}, inv_{}; std::vector<usize> size_{}, dep_{}; }; } // namespace zawa using namespace zawa; // #include "atcoder/modint" // using mint = atcoder::modint998244353; #include <set> using namespace std; struct M { using Element = int; static Element identity() { return (int)1e9; } static Element operation(Element L, Element R) { return min(L, R); } }; int N, Q; int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cin >> N; vector<vector<int>> g(N); for (int i = 0 ; i < N - 1 ; i++) { int u, v; cin >> u >> v; u--; v--; g[u].push_back(v); g[v].push_back(u); } HeavyLightDecomposition hld{g}; SegmentTree<M> seg(N), seg2(N); vector<set<pair<int, int>>> bk(N); auto upd = [&](int u, int v) -> void { pair<int, int> cur{hld.depth(v), v}; auto it = bk[u].find(cur); if (it != bk[u].end()) bk[u].erase(it); else bk[u].insert(cur); seg.assign(hld[u], bk[u].size() ? (bk[u].begin()->first - 2 * (int)hld.depth(u)) : M::identity()); seg2.assign(hld[u], bk[u].size() ? bk[u].begin()->first : M::identity()); }; vector<int> deep(N); for (int i = 0 ; i < N ; i++) { int tp = hld.top(i); if (hld.depth(deep[tp]) < hld.depth(i)) deep[tp] = i; } auto leaf_prod = [&](int v) -> int { int u = deep[hld.top(v)]; tie(u, v) = minmax({hld[u], hld[v]}); return seg2.product(u, v); }; cin >> Q; while (Q--) { int T, V; cin >> T >> V; V--; if (T == 1) { for (auto [u, v] : hld(V, 0)) { upd(u, V); if (u != v) upd(v, V); } } else if (T == 2) { // for (int i = 0 ; i < N ; i++) { // cout << i + 1 << " : "; // for (auto [p, q] : bk[i]) cout << '(' << p << ',' << q + 1 << ')'; // cout << endl; // } int ans = M::identity(); for (auto [u, v] : hld(V, 0)) { tie(u, v) = minmax({hld[u], hld[v]}); ans = min<int>(ans, seg.product(u, v + 1)); if (hld.depth(u) > hld.depth(v)) { ans = min(ans, leaf_prod(u) - 2 * (int)hld.depth(u)); } else { ans = min(ans, leaf_prod(v) - 2 * (int)hld.depth(v)); } } // cout << ans << " add " << hld.depth(V) << endl; ans += hld.depth(V); cout << ans << '\n'; } else assert(false); } }