結果
問題 | No.900 aδδitivee |
ユーザー |
![]() |
提出日時 | 2019-10-04 23:09:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 300 ms / 2,000 ms |
コード長 | 7,918 bytes |
コンパイル時間 | 3,131 ms |
コンパイル使用メモリ | 216,296 KB |
最終ジャッジ日時 | 2025-01-07 20:47:13 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 |
ソースコード
#include <bits/stdc++.h>#define loop(n) for (int ngtkana_is_genius = 0; ngtkana_is_genius < int(n); ngtkana_is_genius++)#define rep(i, begin, end) for(int i = int(begin); i < int(end); i++)#define all(v) v.begin(), v.end()#define rand(l, r) std::uniform_int_distribution<>(l, r)(mt)using lint = long long;auto cmn = [](auto& a, auto b){if (a > b) {a = b; return true;} return false;};auto cmx = [](auto& a, auto b){if (a < b) {a = b; return true;} return false;};void debug_impl() { std::cerr << std::endl; }template <typename Head, typename... Tail>void debug_impl(Head head, Tail... tail){std::cerr << " " << head;debug_impl(tail...);}#ifndef STOPIT#define debug(...)\std::cerr << std::boolalpha << "[" << #__VA_ARGS__ << "]:";\debug_impl(__VA_ARGS__);\std::cerr << std::noboolalpha;#else#define debug 0;#endiftemplate <typename T>auto make_vector_impl(size_t sz, T t) {return std::vector<T>(sz, t);}template <size_t N, typename T, typename U, std::enable_if_t<N == 1, std::nullptr_t> = nullptr>auto make_vector(size_t sz, U u) {return make_vector_impl(sz, T(u));}template <size_t N, typename T, std::enable_if_t<N == 1, std::nullptr_t> = nullptr>auto make_vector(size_t sz) {return std::vector<T>(sz);}template <size_t N, typename T, typename... Args, std::enable_if_t<N != 1, std::nullptr_t> = nullptr>auto make_vector(size_t a, Args... args) {return make_vector_impl(a, make_vector<N - 1, T>(args...));}template <typename T, typename Size_t>auto& at(T& t, Size_t i) {return t.at(i);}template <typename T, typename Size_t, typename... Args>auto& at(T& t, Size_t i, Args... args) {return at(t.at(i), args...);}template < typename Container, typename Value = typename Container::value_type, std::enable_if_t<!std::is_same< Container, std::string >::value, std::nullptr_t> = nullptr>std::istream& operator>> (std::istream& is, Container& v){ for (auto & x : v) { is >> x; } return is; }template < typename Container, typename Value = typename Container::value_type, std::enable_if_t<!std::is_same< Container, std::string >::value, std::nullptr_t> = nullptr >std::ostream& operator<< (std::ostream& os, Container const& v) {os << "{";for (auto it = v.begin(); it != v.end(); it++){os << (it != v.begin() ? "," : "") << *it;}return os << "}";}template < template < typename ... > class Tuple, typename... Args, std::size_t ... Inds, std::size_t = std::tuple_size< Tuple < Args ... > >::value>std::istream& tuple_input_impl(std::istream& os, Tuple<Args...>& tuple, std::integer_sequence<std::size_t, Inds...>){ (void)std::initializer_list<int>{((void)(os >> std::get< Inds >(tuple)), 0)...}; return os; }template < template < typename ... > class Tuple, typename... Args, std::size_t = std::tuple_size< Tuple < Args ... > >::value >std::istream& operator>> (std::istream& os, Tuple<Args...>& tuple){ return tuple_input_impl(os, tuple, std::index_sequence_for<Args...>()); }template < template < typename ... > class Tuple, typename... Args, std::size_t ... Inds, std::size_t = std::tuple_size< Tuple < Args ... > >::value>std::ostream& tuple_output_impl(std::ostream& os, const Tuple<Args...>& tuple, std::integer_sequence<std::size_t, Inds...>){ os << "("; (void)std::initializer_list<int>{((void)(os << (Inds > 0 ? "," : "") << std::get< Inds >(tuple)), 0)...}; return os << ")"; }template < template < typename ... > class Tuple, typename... Args, std::size_t = std::tuple_size< Tuple < Args ... > >::value >std::ostream& operator<< (std::ostream& os, const Tuple<Args...>& tuple){ return tuple_output_impl(os, tuple, std::index_sequence_for<Args...>()); }template<typename Value, typename BinaryOp>class segment_tree {int sz, n, N;BinaryOp op;Value id;std::vector<Value> table;auto& op_eq(Value& x, Value y) const { return x = op(x, y); }void merge(int u){ table.at(u) = op(table.at(2 * u), table.at(2 * u + 1)); }Value query_impl(int l, int r, int k, int L, int R) const {return l <= L && R <= r? table.at(k): R <= l || r <= L? id: op(query_impl(l, r, 2 * k, L, (L + R) / 2),query_impl(l, r, 2 * k + 1, (L + R) / 2, R));}public:segment_tree(int sz, BinaryOp op, Value id):sz (sz),n (std::pow(2, int(std::log2(2 * sz - 1)))),N (n * 2),op (op),id (id),table (N, id){}auto& at(int i) { return table.at(n + i); }auto& at(int i) const { return table.at(n + i); }auto collect() const {auto ret = std::vector<Value>(sz);for (auto i = 0; i < sz; i++){ ret.at(i) = at(i); }return ret;}auto query(int l, int r) const{ return query_impl(l, r, 1, 0, n); }void build_oneline(int i){ for (i += n, i /= 2; i > 0; i /= 2) merge(i); }void build(){ for (auto i = 1; i < n; i++) merge(i); }void update (int u, Value val) {at(u) = val;build_oneline(u);}void add (int u, Value val) {at(u) += val;build_oneline(u);}};template<typename Value, typename BinaryOp>auto make_segment_tree(int sz, BinaryOp op, Value id){ return segment_tree<Value, BinaryOp>(sz, std::move(op), id); }template< typename F >class fixed_point : F {public:explicit constexpr fixed_point (F&& f) noexcept: F(std::forward< F >(f)) {}template< typename ... Args >constexpr decltype(auto) operator()(Args&& ... args) const{ return F::operator()(*this, std::forward< Args >(args)...); }};template< typename F >static inline constexpr decltype(auto) fix (F&& f) noexcept{ return fixed_point< F >{std::forward< F >(f)}; }int main() {std::cin.tie(0); std::cin.sync_with_stdio(false);int n; std::cin >> n;auto graph = make_vector< 2, std::pair< int, lint > >(n, 0);loop(n - 1) {int u, v, w;std::cin >> u >> v >> w;graph.at(u).emplace_back(v, w);graph.at(v).emplace_back(u, w);}// queriesint q; std::cin >> q;std::vector< std::tuple< int, int, int > > queries(q);std::vector< std::vector< int > > query_inds(n);rep(i, 0, n) {int c; std::cin >> c;if (c == 1) {int a, x; std::cin >> a >> x;queries.at(i) = {1, a, x};query_inds.at(a).emplace_back(i);} else {int b; std::cin >> b;queries.at(i) = {2, b, -1};query_inds.at(b).emplace_back(i);}}auto a = make_segment_tree(n,[](auto x, auto y){ return x + y; },0LL);auto b = a;auto add = [&] (auto&& qids, int sign, int d) {for (auto qid : qids) {int c, u; lint x; std::tie(c, u, x) = queries.at(qid);if (c == 1) {a.add(qid, -d * x * sign);b.add(qid, x * sign);}}};std::vector< lint > ans(q, -1);auto answer = [&] (auto&& qids, int d, lint wd) {for (auto qid : qids) {int c, u; lint x; std::tie(c, u, x) = queries.at(qid);if (c == 2) {auto f = a.query(0, qid);auto g = b.query(0, qid) * d;auto h = wd;// debug(a.collect());// debug(b.collect());// debug("answer", u, qid, f, g, h);// std::cout << std::endl;ans.at(qid) = a.query(0, qid) + b.query(0, qid) * d + wd;}}};auto root = 0;fix ([&](auto&& dfs, int crr, int prv, int d, lint wd) -> void {auto const & qids = query_inds.at(crr);answer(qids, d, wd);add(qids, +1, d);for (auto const& e : graph.at(crr)) {int nxt; lint w; std::tie(nxt, w) = e;if (nxt == prv) continue;dfs(nxt, crr, d + 1, wd + w);}add(qids, -1, d);})(root, root, 0, 0);rep(i, 0, q) {if (std::get< 0 >(queries.at(i)) == 2){ std::cout << ans.at(i) << std::endl; }}return 0;}