#include #define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i)) #define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i)) #define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i)) #define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i)) #define ALL(x) std::begin(x), std::end(x) #define dump(x) cerr << #x " = " << x << endl using namespace std; template using reversed_priority_queue = priority_queue, greater >; template inline void chmax(T & a, U const & b) { a = max(a, b); } template inline void chmin(T & a, U const & b) { a = min(a, b); } template auto make_table(X x, T a) { return vector(x, a); } template auto make_table(X x, Y y, Z z, Zs... zs) { auto cont = make_table(y, z, zs...); return vector(x, cont); } template ostream & operator << (ostream & out, vector const & xs) { REP (i, (int)xs.size() - 1) out << xs[i] << ' '; if (not xs.empty()) out << xs.back(); return out; } /** * @arg g must be a tree * @note O(n) time * @note O(n) space on heap */ struct subtree_info_t { int parent; // in the entire tree int depth; // in the entire tree int size; // of the subtree int height; // of the subtree }; vector prepare_subtree_info(vector > const & g, int root) { int n = g.size(); vector info(n, (subtree_info_t) { -1, -1, -1, -1 }); vector topological(n); topological[0] = root; info[root].parent = root; info[root].depth = 0; int r = 1; for (int l = 0; l < r; ++ l) { int i = topological[l]; for (int j : g[i]) if (j != info[i].parent) { topological[r ++] = j; info[j].parent = i; info[j].depth = info[i].depth + 1; } } while ((-- r) >= 0) { int i = topological[r]; info[i].size = 1; info[i].height = 0; for (int j : g[i]) if (j != info[i].parent) { info[i].size += info[j].size; info[i].height = max(info[i].height, info[j].height + 1); } } info[root].parent = -1; return info; } /** * @brief euler tour * @arg g must be a tree, directed or undirected * @note for constraints, see the unittest */ void do_euler_tour(vector > const & g, int root, vector & tour, vector & left, vector & right) { int n = g.size(); tour.clear(); left.resize(n); right.resize(n); function go = [&](int x, int parent) { left[x] = tour.size(); tour.push_back(x); for (int y : g[x]) if (y != parent) { go(y, x); } right[x] = tour.size(); tour.push_back(x); }; go(root, -1); } template struct dual_segment_tree { typedef typename OperatorMonoid::value_type operator_type; typedef typename OperatorMonoid::target_type value_type; int n; std::vector f; std::vector a; const OperatorMonoid op; dual_segment_tree() = default; dual_segment_tree(int a_n, value_type initial_value, OperatorMonoid const & a_op = OperatorMonoid()) : op(a_op) { n = 1; while (n < a_n) n *= 2; a.resize(n, initial_value); f.resize(n - 1, op.unit()); } value_type point_get(int i) { // 0-based value_type acc = a[i]; for (i = (i + n) / 2; i > 0; i /= 2) { // 1-based acc = op.apply(f[i - 1], acc); } return acc; } void range_apply(int l, int r, operator_type z) { // 0-based, [l, r) assert (0 <= l and l <= r and r <= n); range_apply(0, 0, n, l, r, z); } void range_apply(int i, int il, int ir, int l, int r, operator_type z) { if (l <= il and ir <= r) { // 0-based if (i < f.size()) { f[i] = op.append(z, f[i]); } else { a[i - n + 1] = op.apply(z, a[i - n + 1]); } } else if (ir <= l or r <= il) { // nop } else { range_apply(2 * i + 1, il, (il + ir) / 2, 0, n, f[i]); range_apply(2 * i + 2, (il + ir) / 2, ir, 0, n, f[i]); f[i] = op.unit(); range_apply(2 * i + 1, il, (il + ir) / 2, l, r, z); range_apply(2 * i + 2, (il + ir) / 2, ir, l, r, z); } } void point_set(int i, value_type z) { range_apply(i, i + 1, op.unit()); // to flush lazed ops a[i + n - 1] = z; // bug?? } }; struct add_linear_function_monoid { typedef std::pair value_type; typedef std::pair target_type; add_linear_function_monoid() = default; value_type unit() const { return std::make_pair(0, 0); } value_type append(value_type g, value_type f) const { int64_t fst = f.first + g.first; int64_t snd = f.second + g.second; return std::make_pair(fst, snd); } target_type apply(value_type f, target_type x) const { int64_t fst = f.first + x.first; int64_t snd = f.second + x.second; return std::make_pair(fst, snd); } }; int main() { // input int n; cin >> n; vector > g(n); vector > edges; REP (i, n - 1) { int x, y; int64_t c; cin >> x >> y >> c; g[x].push_back(y); g[y].push_back(x); edges.emplace_back(x, y, c); } // prepare const int root = 0; auto info = prepare_subtree_info(g, root); vector tour, left, right; do_euler_tour(g, root, tour, left, right); dual_segment_tree segtree(2 * n, make_pair(0, 0)); for (auto edge : edges) { int x, y; int64_t c; tie(x, y, c) = edge; int z = (left[x] <= left[y] and left[y] < right[x] ? y : x); segtree.range_apply(left[z], right[z], make_pair(0, c)); } // query int q; cin >> q; while (q --) { int type; cin >> type; if (type == 1) { int x; int64_t c; cin >> x >> c; segtree.range_apply(left[x], right[x], make_pair(c, - c * info[x].depth)); } else if (type == 2) { int y; cin >> y; int64_t a, b; tie(a, b) = segtree.point_get(left[y]); cout << a * info[y].depth + b << endl; } } return 0; }