結果
問題 | No.1197 モンスターショー |
ユーザー |
![]() |
提出日時 | 2022-09-25 14:31:37 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 448 ms / 3,000 ms |
コード長 | 14,406 bytes |
コンパイル時間 | 2,304 ms |
コンパイル使用メモリ | 202,560 KB |
実行使用メモリ | 19,312 KB |
最終ジャッジ日時 | 2024-06-01 22:17:26 |
合計ジャッジ時間 | 13,201 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 59 ms
16,228 KB |
testcase_08 | AC | 152 ms
10,880 KB |
testcase_09 | AC | 173 ms
16,728 KB |
testcase_10 | AC | 255 ms
16,256 KB |
testcase_11 | AC | 174 ms
7,296 KB |
testcase_12 | AC | 149 ms
6,940 KB |
testcase_13 | AC | 71 ms
11,392 KB |
testcase_14 | AC | 280 ms
11,648 KB |
testcase_15 | AC | 200 ms
7,168 KB |
testcase_16 | AC | 287 ms
18,252 KB |
testcase_17 | AC | 305 ms
18,456 KB |
testcase_18 | AC | 119 ms
8,064 KB |
testcase_19 | AC | 248 ms
16,316 KB |
testcase_20 | AC | 52 ms
7,168 KB |
testcase_21 | AC | 181 ms
6,940 KB |
testcase_22 | AC | 19 ms
6,940 KB |
testcase_23 | AC | 289 ms
12,032 KB |
testcase_24 | AC | 219 ms
12,032 KB |
testcase_25 | AC | 131 ms
9,856 KB |
testcase_26 | AC | 274 ms
10,112 KB |
testcase_27 | AC | 306 ms
17,496 KB |
testcase_28 | AC | 225 ms
10,624 KB |
testcase_29 | AC | 163 ms
11,776 KB |
testcase_30 | AC | 127 ms
12,672 KB |
testcase_31 | AC | 117 ms
11,008 KB |
testcase_32 | AC | 112 ms
6,940 KB |
testcase_33 | AC | 67 ms
9,856 KB |
testcase_34 | AC | 448 ms
19,312 KB |
testcase_35 | AC | 432 ms
19,276 KB |
testcase_36 | AC | 446 ms
19,248 KB |
testcase_37 | AC | 440 ms
19,256 KB |
testcase_38 | AC | 438 ms
19,192 KB |
testcase_39 | AC | 445 ms
19,212 KB |
testcase_40 | AC | 177 ms
18,864 KB |
testcase_41 | AC | 2 ms
6,940 KB |
testcase_42 | AC | 2 ms
6,940 KB |
ソースコード
#include <algorithm> #include <array> #include <bitset> #include <cassert> #include <chrono> #include <cmath> #include <complex> #include <deque> #include <forward_list> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iostream> #include <limits> #include <list> #include <map> #include <numeric> #include <queue> #include <random> #include <set> #include <sstream> #include <stack> #include <string> #include <tuple> #include <type_traits> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> using namespace std; using lint = long long; using pint = pair<int, int>; using plint = pair<lint, lint>; struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_; #define ALL(x) (x).begin(), (x).end() #define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++) #define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--) #define REP(i, n) FOR(i,0,n) #define IREP(i, n) IFOR(i,0,n) template <typename T, typename V> void ndarray(vector<T>& vec, const V& val, int len) { vec.assign(len, val); } template <typename T, typename V, typename... Args> void ndarray(vector<T>& vec, const V& val, int len, Args... args) { vec.resize(len), for_each(begin(vec), end(vec), [&](T& v) { ndarray(v, val, args...); }); } template <typename T> bool chmax(T &m, const T q) { return m < q ? (m = q, true) : false; } template <typename T> bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; } int floor_lg(long long x) { return x <= 0 ? -1 : 63 - __builtin_clzll(x); } template <class T1, class T2> std::pair<T1, T2> operator+(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first + r.first, l.second + r.second); } template <class T1, class T2> std::pair<T1, T2> operator-(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first - r.first, l.second - r.second); } template <class T> std::vector<T> sort_unique(std::vector<T> vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; } template <class T> int arglb(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x)); } template <class T> int argub(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x)); } template <class IStream, class T> IStream &operator>>(IStream &is, std::vector<T> &vec) { for (auto &v : vec) is >> v; return is; } template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec); template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr); template <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec); template <class OStream, class T, class U> OStream &operator<<(OStream &os, const pair<T, U> &pa); template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec); template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec); template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec); template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec); template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa); template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp); template <class OStream, class TK, class TV, class TH> OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp); template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl); template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec) { os << '['; for (auto v : vec) os << v << ','; os << ']'; return os; } template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr) { os << '['; for (auto v : arr) os << v << ','; os << ']'; return os; } #if __cplusplus >= 201703L template <class... T> std::istream &operator>>(std::istream &is, std::tuple<T...> &tpl) { std::apply([&is](auto &&... args) { ((is >> args), ...);}, tpl); return is; } template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl) { os << '('; std::apply([&os](auto &&... args) { ((os << args << ','), ...);}, tpl); return os << ')'; } #endif template <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ','; os << ']'; return os; } template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa) { return os << '(' << pa.first << ',' << pa.second << ')'; } template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; } template <class OStream, class TK, class TV, class TH> OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; } #ifdef HITONANODE_LOCAL const string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m", BRIGHT_RED = "\033[1;31m", BRIGHT_CYAN = "\033[1;36m", NORMAL_CROSSED = "\033[0;9;37m", RED_BACKGROUND = "\033[1;41m", NORMAL_FAINT = "\033[0;2m"; #define dbg(x) std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << std::endl #define dbgif(cond, x) ((cond) ? std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << std::endl : std::cerr) #else #define dbg(x) ((void)0) #define dbgif(cond, x) ((void)0) #endif // Heavy-Light Decomposition of trees // Based on http://beet-aizu.hatenablog.com/entry/2017/12/12/235950 struct HeavyLightDecomposition { int V; int k; int nb_heavy_path; std::vector<std::vector<int>> e; std::vector<int> par; // par[i] = parent of vertex i (Default: -1) std::vector<int> depth; // depth[i] = distance between root and vertex i std::vector<int> subtree_sz; // subtree_sz[i] = size of subtree whose root is i std::vector<int> heavy_child; // heavy_child[i] = child of vertex i on heavy path (Default: -1) std::vector<int> tree_id; // tree_id[i] = id of tree vertex i belongs to std::vector<int> aligned_id, aligned_id_inv; // aligned_id[i] = aligned id for vertex i (consecutive on heavy edges) std::vector<int> head; // head[i] = id of vertex on heavy path of vertex i, nearest to root std::vector<int> head_ids; // consist of head vertex id's std::vector<int> heavy_path_id; // heavy_path_id[i] = heavy_path_id for vertex [i] HeavyLightDecomposition(int sz = 0) : V(sz), k(0), nb_heavy_path(0), e(sz), par(sz), depth(sz), subtree_sz(sz), heavy_child(sz), tree_id(sz, -1), aligned_id(sz), aligned_id_inv(sz), head(sz), heavy_path_id(sz, -1) {} void add_edge(int u, int v) { e[u].emplace_back(v); e[v].emplace_back(u); } void _build_dfs(int root) { std::stack<std::pair<int, int>> st; par[root] = -1; depth[root] = 0; st.emplace(root, 0); while (!st.empty()) { int now = st.top().first; int &i = st.top().second; if (i < (int)e[now].size()) { int nxt = e[now][i++]; if (nxt == par[now]) continue; par[nxt] = now; depth[nxt] = depth[now] + 1; st.emplace(nxt, 0); } else { st.pop(); int max_sub_sz = 0; subtree_sz[now] = 1; heavy_child[now] = -1; for (auto nxt : e[now]) { if (nxt == par[now]) continue; subtree_sz[now] += subtree_sz[nxt]; if (max_sub_sz < subtree_sz[nxt]) max_sub_sz = subtree_sz[nxt], heavy_child[now] = nxt; } } } } void _build_bfs(int root, int tree_id_now) { std::queue<int> q({root}); while (!q.empty()) { int h = q.front(); q.pop(); head_ids.emplace_back(h); for (int now = h; now != -1; now = heavy_child[now]) { tree_id[now] = tree_id_now; aligned_id[now] = k++; aligned_id_inv[aligned_id[now]] = now; heavy_path_id[now] = nb_heavy_path; head[now] = h; for (int nxt : e[now]) if (nxt != par[now] and nxt != heavy_child[now]) q.push(nxt); } nb_heavy_path++; } } void build(std::vector<int> roots = {0}) { int tree_id_now = 0; for (auto r : roots) { _build_dfs(r); _build_bfs(r, tree_id_now++); } } template <typename Monoid> std::vector<Monoid> segtree_rearrange(const std::vector<Monoid> &data) const { assert(int(data.size()) == V); std::vector<Monoid> ret; ret.reserve(V); for (int i = 0; i < V; i++) ret.emplace_back(data[aligned_id_inv[i]]); return ret; } // query for vertices on path [u, v] (INCLUSIVE) void for_each_vertex(int u, int v, const std::function<void(int ancestor, int descendant)> &f) const { while (true) { if (aligned_id[u] > aligned_id[v]) std::swap(u, v); f(std::max(aligned_id[head[v]], aligned_id[u]), aligned_id[v]); if (head[u] == head[v]) break; v = par[head[v]]; } } void for_each_vertex_noncommutative( int from, int to, const std::function<void(int ancestor, int descendant)> &fup, const std::function<void(int ancestor, int descendant)> &fdown) const { int u = from, v = to; const int lca = lowest_common_ancestor(u, v), dlca = depth[lca]; while (u >= 0 and depth[u] > dlca) { const int p = (depth[head[u]] > dlca ? head[u] : lca); fup(aligned_id[p] + (p == lca), aligned_id[u]), u = par[p]; } std::vector<std::pair<int, int>> lrs; while (v >= 0 and depth[v] >= dlca) { const int p = (depth[head[v]] >= dlca ? head[v] : lca); lrs.emplace_back(p, v), v = par[p]; } std::reverse(lrs.begin(), lrs.end()); for (const auto &lr : lrs) fdown(aligned_id[lr.first], aligned_id[lr.second]); } // query for edges on path [u, v] void for_each_edge(int u, int v, const std::function<void(int, int)> &f) const { while (true) { if (aligned_id[u] > aligned_id[v]) std::swap(u, v); if (head[u] != head[v]) { f(aligned_id[head[v]], aligned_id[v]); v = par[head[v]]; } else { if (u != v) f(aligned_id[u] + 1, aligned_id[v]); break; } } } // lowest_common_ancestor: O(logV) int lowest_common_ancestor(int u, int v) const { assert(tree_id[u] == tree_id[v] and tree_id[u] >= 0); while (true) { if (aligned_id[u] > aligned_id[v]) std::swap(u, v); if (head[u] == head[v]) return u; v = par[head[v]]; } } int distance(int u, int v) const { assert(tree_id[u] == tree_id[v] and tree_id[u] >= 0); return depth[u] + depth[v] - 2 * depth[lowest_common_ancestor(u, v)]; } }; #include <atcoder/lazysegtree> namespace rangeaddrangesum { using S = pair<lint, int>; // (sum, #) S op(S l, S r) { return l + r; } S e() { return {0, 0}; } using F = int; F composition(F fnew, F gold) { return fnew + gold; } F id() { return 0; } S mapping(F f, S x) { return {x.first + lint(x.second) * f, x.second}; } using Segtree = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>; }; // namespace rangeaddrangesum int main() { int N, K, Q; cin >> N >> K >> Q; vector<int> C(K); cin >> C; for (auto &x : C) --x; dbg(C); HeavyLightDecomposition hld(N); REP(e, N - 1) { int a, b; cin >> a >> b; --a, --b; hld.add_edge(a, b); } hld.build({0}); dbg(hld.depth); rangeaddrangesum::Segtree tree(vector<pair<lint, int>>(N, make_pair(0, 1))); lint depth_sum = 0; for (auto x : C) { hld.for_each_vertex(0, x, [&](int l, int r) { tree.apply(l, r + 1, 1); }); depth_sum += hld.depth.at(x); } while (Q--) { dbg(depth_sum); int tp; cin >> tp; if (tp == 1) { int p, d; cin >> p >> d; --p, --d; hld.for_each_vertex(0, C.at(p), [&](int l, int r) { tree.apply(l, r + 1, -1); }); depth_sum -= hld.depth.at(C.at(p)); C.at(p) = d; hld.for_each_vertex(0, C.at(p), [&](int l, int r) { tree.apply(l, r + 1, 1); }); depth_sum += hld.depth.at(C.at(p)); } else { int e; cin >> e; --e; lint ret = depth_sum + lint(K) * hld.depth.at(e); dbg(ret); dbg(tree.prod(0, 3)); hld.for_each_vertex(0, e, [&](int l, int r) { ret -= tree.prod(l, r + 1).first * 2; }); dbg(ret); cout << ret + K * 2 << '\n'; } } }