結果

問題 No.900 aδδitivee
ユーザー ngtkanangtkana
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

#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;
#endif
template <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);
}
// queries
int 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0