// competitive-verifier: PROBLEM #pragma GCC optimize("Ofast,fast-math,unroll-all-loops") #include #if !defined(ATCODER) && !defined(EVAL) #pragma GCC target("sse4.2,avx2,bmi2") #endif template constexpr bool chmax(T &a, const U &b) { return a < (T)b ? a = (T)b, true : false; } template constexpr bool chmin(T &a, const U &b) { return (T)b < a ? a = (T)b, true : false; } constexpr std::int64_t INF = 1000000000000000003; constexpr int Inf = 1000000003; constexpr double EPS = 1e-7; constexpr double PI = 3.14159265358979323846; #define FOR(i, m, n) for (int i = (m); i < int(n); ++i) #define FORR(i, m, n) for (int i = (m) - 1; i >= int(n); --i) #define FORL(i, m, n) for (std::int64_t i = (m); i < std::int64_t(n); ++i) #define rep(i, n) FOR (i, 0, n) #define repn(i, n) FOR (i, 1, n + 1) #define repr(i, n) FORR (i, n, 0) #define repnr(i, n) FORR (i, n + 1, 1) #define all(s) (s).begin(), (s).end() struct Sonic { Sonic() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout << std::fixed << std::setprecision(20); } constexpr void operator()() const {} } sonic; struct increment_impl { template const increment_impl &operator>>(std::vector &v) const { for (auto &x : v) ++x; return *this; } } Inc; struct decrement_impl { template const decrement_impl &operator>>(std::vector &v) const { for (auto &x : v) --x; return *this; } } Dec; struct sort_impl { template const sort_impl &operator>>(std::vector &v) const { std::sort(v.begin(), v.end()); return *this; } } Sort; struct unique_impl { template const unique_impl &operator>>(std::vector &v) const { std::sort(v.begin(), v.end()); v.erase(std::unique(v.begin(), v.end()), v.end()); return *this; } } Uniq; using namespace std; using ll = std::int64_t; using ld = long double; template std::istream &operator>>(std::istream &is, std::pair &p) { return is >> p.first >> p.second; } template std::istream &operator>>(std::istream &is, std::vector &v) { for (T &i : v) is >> i; return is; } template std::ostream &operator<<(std::ostream &os, const std::pair &p) { return os << '(' << p.first << ',' << p.second << ')'; } template std::ostream &operator<<(std::ostream &os, const std::vector &v) { for (auto it = v.begin(); it != v.end(); ++it) os << (it == v.begin() ? "" : " ") << *it; return os; } template void co(Head &&head, Tail &&...tail) { if constexpr (sizeof...(tail) == 0) std::cout << head << '\n'; else std::cout << head << ' ', co(std::forward(tail)...); } template void ce(Head &&head, Tail &&...tail) { if constexpr (sizeof...(tail) == 0) std::cerr << head << '\n'; else std::cerr << head << ' ', ce(std::forward(tail)...); } void Yes(bool is_correct = true) { std::cout << (is_correct ? "Yes\n" : "No\n"); } void No(bool is_not_correct = true) { Yes(!is_not_correct); } void YES(bool is_correct = true) { std::cout << (is_correct ? "YES\n" : "NO\n"); } void NO(bool is_not_correct = true) { YES(!is_not_correct); } void Takahashi(bool is_correct = true) { std::cout << (is_correct ? "Takahashi" : "Aoki") << '\n'; } void Aoki(bool is_not_correct = true) { Takahashi(!is_not_correct); } /// @brief 重み付きグラフ template struct Graph { private: struct _edge { constexpr _edge() : _from(), _to(), _weight() {} constexpr _edge(int from, int to, T weight) : _from(from), _to(to), _weight(weight) {} constexpr bool operator<(const _edge &rhs) const { return weight() < rhs.weight(); } constexpr bool operator>(const _edge &rhs) const { return rhs < *this; } constexpr int from() const { return _from; } constexpr int to() const { return _to; } constexpr T weight() const { return _weight; } private: int _from, _to; T _weight; }; public: using edge_type = typename Graph::_edge; Graph() : _size(), edges() {} Graph(int v) : _size(v), edges(v) {} const auto &operator[](int i) const { return edges[i]; } auto &operator[](int i) { return edges[i]; } const auto begin() const { return edges.begin(); } auto begin() { return edges.begin(); } const auto end() const { return edges.end(); } auto end() { return edges.end(); } constexpr int size() const { return _size; } void add_edge(const edge_type &e) { edges[e.from()].emplace_back(e); } void add_edge(int from, int to, T weight = T(1)) { edges[from].emplace_back(from, to, weight); } void add_edges(int from, int to, T weight = T(1)) { edges[from].emplace_back(from, to, weight); edges[to].emplace_back(to, from, weight); } void input_edge(int m, int base = 1) { for (int i = 0; i < m; ++i) { int from, to; T weight; std::cin >> from >> to >> weight; add_edge(from - base, to - base, weight); } } void input_edges(int m, int base = 1) { for (int i = 0; i < m; ++i) { int from, to; T weight; std::cin >> from >> to >> weight; add_edges(from - base, to - base, weight); } } private: int _size; std::vector> edges; }; /// @brief 重みなしグラフ template <> struct Graph { private: struct _edge { constexpr _edge() : _from(), _to() {} constexpr _edge(int from, int to) : _from(from), _to(to) {} constexpr int from() const { return _from; } constexpr int to() const { return _to; } constexpr int weight() const { return 1; } constexpr bool operator<(const _edge &rhs) const { return weight() < rhs.weight(); } constexpr bool operator>(const _edge &rhs) const { return rhs < *this; } private: int _from, _to; }; public: using edge_type = typename Graph::_edge; Graph() : _size(), edges() {} Graph(int v) : _size(v), edges(v) {} const auto &operator[](int i) const { return edges[i]; } auto &operator[](int i) { return edges[i]; } const auto begin() const { return edges.begin(); } auto begin() { return edges.begin(); } const auto end() const { return edges.end(); } auto end() { return edges.end(); } constexpr int size() const { return _size; } void add_edge(const edge_type &e) { edges[e.from()].emplace_back(e); } void add_edge(int from, int to) { edges[from].emplace_back(from, to); } void add_edges(int from, int to) { edges[from].emplace_back(from, to); edges[to].emplace_back(to, from); } void input_edge(int m, int base = 1) { for (int i = 0; i < m; ++i) { int from, to; std::cin >> from >> to; add_edge(from - base, to - base); } } void input_edges(int m, int base = 1) { for (int i = 0; i < m; ++i) { int from, to; std::cin >> from >> to; add_edges(from - base, to - base); } } private: int _size; std::vector> edges; }; template struct Add { using value_type = T; static constexpr T id() { return T(); } static constexpr T op(const T &lhs, const T &rhs) { return lhs + rhs; } template static constexpr U f(T lhs, U rhs) { return lhs + rhs; } }; template struct Mul { using value_type = T; static constexpr T id() { return T(1); } static constexpr T op(const T &lhs, const T &rhs) { return lhs * rhs; } template static constexpr U f(T lhs, U rhs) { return lhs * rhs; } }; template struct And { using value_type = T; static constexpr T id() { return std::numeric_limits::max(); } static constexpr T op(const T &lhs, const T &rhs) { return lhs & rhs; } template static constexpr U f(T lhs, U rhs) { return lhs & rhs; } }; template struct Or { using value_type = T; static constexpr T id() { return T(); } static constexpr T op(const T &lhs, const T &rhs) { return lhs | rhs; } template static constexpr U f(T lhs, U rhs) { return lhs | rhs; } }; template struct Xor { using value_type = T; static constexpr T id() { return T(); } static constexpr T op(const T &lhs, const T &rhs) { return lhs ^ rhs; } template static constexpr U f(T lhs, U rhs) { return lhs ^ rhs; } }; template struct Min { using value_type = T; static constexpr T id() { return std::numeric_limits::max(); } static constexpr T op(const T &lhs, const T &rhs) { return std::min(lhs, rhs); } template static constexpr U f(T lhs, U rhs) { return std::min((U)lhs, rhs); } }; template struct Max { using value_type = T; static constexpr T id() { return std::numeric_limits::lowest(); } static constexpr T op(const T &lhs, const T &rhs) { return std::max(lhs, rhs); } template static constexpr U f(T lhs, U rhs) { return std::max((U)lhs, rhs); } }; template struct Gcd { using value_type = T; static constexpr T id() { return std::numeric_limits::max(); } static constexpr T op(const T &lhs, const T &rhs) { return lhs == Gcd::id() ? rhs : (rhs == Gcd::id() ? lhs : std::gcd(lhs, rhs)); } }; template struct Lcm { using value_type = T; static constexpr T id() { return std::numeric_limits::max(); } static constexpr T op(const T &lhs, const T &rhs) { return lhs == Lcm::id() ? rhs : (rhs == Lcm::id() ? lhs : std::lcm(lhs, rhs)); } }; template struct Update { using value_type = T; static constexpr T id() { return std::numeric_limits::max(); } static constexpr T op(const T &lhs, const T &rhs) { return lhs == Update::id() ? rhs : lhs; } template static constexpr U f(T lhs, U rhs) { return lhs == Update::id() ? rhs : lhs; } }; template struct Affine { using P = std::pair; using value_type = P; static constexpr P id() { return P(1, 0); } static constexpr P op(P lhs, P rhs) { return {lhs.first * rhs.first, rhs.first * lhs.second + rhs.second}; } }; template struct Rev { using T = typename M::value_type; using value_type = T; static constexpr T id() { return M::id(); } static constexpr T op(T lhs, T rhs) { return M::op(rhs, lhs); } }; // Euler Tour Tree template struct euler_tour_tree { using T = typename M::value_type; struct node_t { int u, v; T val, sum; int sz; node_t *par, *l, *r; node_t(int _u, int _v, const T& _val = M::id()) : u(_u), v(_v), val(_val), sum(_val), sz(u == v ? 1 : 0), par(nullptr), l(nullptr), r(nullptr) {} }; int n; std::vector vertex_node; std::map, node_t*> edge_node; euler_tour_tree(int _n) : n(_n) { vertex_node.resize(n, nullptr); for (int i = 0; i < n; ++i) { vertex_node[i] = new node_t(i, i); } } euler_tour_tree(const std::vector& v) : n(v.size()) { vertex_node.resize(n, nullptr); for (int i = 0; i < n; ++i) { vertex_node[i] = new node_t(i, i, v[i]); } } ~euler_tour_tree() { for (auto nd : vertex_node) delete nd; for (auto& p : edge_node) delete p.second; } bool is_root(node_t* t) { return !t->par; } void update(node_t* t) { if (!t) return; t->sum = t->val; t->sz = (t->u == t->v) ? 1 : 0; if (t->l) { t->sum = M::op(t->l->sum, t->sum); t->sz += t->l->sz; } if (t->r) { t->sum = M::op(t->sum, t->r->sum); t->sz += t->r->sz; } } void rotate(node_t* t) { node_t* p = t->par; node_t* pp = p->par; if (p->l == t) { p->l = t->r; if (t->r) t->r->par = p; t->r = p; } else { p->r = t->l; if (t->l) t->l->par = p; t->l = p; } p->par = t; t->par = pp; if (pp) { if (pp->l == p) pp->l = t; else pp->r = t; } update(p); update(t); } void splay(node_t* t) { if (!t) return; while (!is_root(t)) { node_t* p = t->par; if (!is_root(p)) { node_t* pp = p->par; if ((pp->l == p) == (p->l == t)) rotate(p); else rotate(t); } rotate(t); } } node_t* join(node_t* l, node_t* r) { if (!l) return r; if (!r) return l; while (l->r) l = l->r; splay(l); l->r = r; r->par = l; update(l); return l; } void reroot(int v) { node_t* nd = vertex_node[v]; splay(nd); node_t* l = nd->l; if (l) { l->par = nullptr; nd->l = nullptr; update(nd); join(nd, l); } } void link(int u, int v) { reroot(u); reroot(v); node_t* uv = new node_t(u, v); node_t* vu = new node_t(v, u); edge_node[{u, v}] = uv; edge_node[{v, u}] = vu; node_t* tu = vertex_node[u]; node_t* tv = vertex_node[v]; splay(tu); splay(tv); join(tu, join(uv, join(tv, vu))); } void cut(int u, int v) { node_t* uv = edge_node[{u, v}]; node_t* vu = edge_node[{v, u}]; edge_node.erase({u, v}); edge_node.erase({v, u}); reroot(u); splay(vu); node_t* C = vu->r; node_t* AB_uv = vu->l; if (C) C->par = nullptr; if (AB_uv) AB_uv->par = nullptr; vu->l = vu->r = nullptr; update(vu); splay(uv); node_t* B = uv->r; node_t* A = uv->l; if (B) B->par = nullptr; if (A) A->par = nullptr; uv->l = uv->r = nullptr; update(uv); join(A, C); delete uv; delete vu; } node_t* get_root(node_t* t) { if (!t) return nullptr; splay(t); while (t->l) t = t->l; splay(t); return t; } bool same(int u, int v) { return get_root(vertex_node[u]) == get_root(vertex_node[v]); } void set(int u, const T& val) { node_t* nd = vertex_node[u]; splay(nd); nd->val = val; update(nd); } T get(int u) { node_t* nd = vertex_node[u]; splay(nd); return nd->val; } T get_subtree(int v, int p = -1) { if (p == -1 || p == v) { node_t* nd = vertex_node[v]; splay(nd); return nd->sum; } auto it_pv = edge_node.find({p, v}); assert(it_pv != edge_node.end()); node_t* pv = it_pv->second; node_t* vp = edge_node[{v, p}]; reroot(p); splay(vp); node_t* C = vp->r; node_t* AB_pv = vp->l; if (C) C->par = nullptr; if (AB_pv) AB_pv->par = nullptr; vp->l = vp->r = nullptr; update(vp); splay(pv); node_t* B = pv->r; node_t* A = pv->l; if (B) B->par = nullptr; if (A) A->par = nullptr; pv->l = pv->r = nullptr; update(pv); T res = B ? B->sum : M::id(); pv->l = A; if (A) A->par = pv; pv->r = B; if (B) B->par = pv; update(pv); vp->l = pv; pv->par = vp; vp->r = C; if (C) C->par = vp; update(vp); return res; } int get_size(int v, int p = -1) { if (p == -1 || p == v) { node_t* nd = vertex_node[v]; splay(nd); return nd->sz; } auto it_pv = edge_node.find({p, v}); assert(it_pv != edge_node.end()); node_t* pv = it_pv->second; node_t* vp = edge_node[{v, p}]; reroot(p); splay(vp); node_t* C = vp->r; node_t* AB_pv = vp->l; if (C) C->par = nullptr; if (AB_pv) AB_pv->par = nullptr; vp->l = vp->r = nullptr; update(vp); splay(pv); node_t* B = pv->r; node_t* A = pv->l; if (B) B->par = nullptr; if (A) A->par = nullptr; pv->l = pv->r = nullptr; update(pv); int res = B ? B->sz : 0; pv->l = A; if (A) A->par = pv; pv->r = B; if (B) B->par = pv; update(pv); vp->l = pv; pv->par = vp; vp->r = C; if (C) C->par = vp; update(vp); return res; } }; void solve() { int n; cin >> n; vector> edge(n - 1); for (auto& [u, v, x] : edge) { cin >> u >> v >> x; --u, --v; } Graph g(2 * n - 1); vector a(2 * n - 1); rep (i, n - 1) { auto [u, v, x] = edge[i]; g.add_edges(u, n + i); g.add_edges(v, n + i); a[n + i] = x; } vector par(2 * n - 1, -1); auto dfs = [&](auto self, int x, int p) -> void { par[x] = p; for (auto e : g[x]) { if (e.to() == p) continue; self(self, e.to(), x); } }; dfs(dfs, 0, -1); euler_tour_tree> et(a); rep (i, n - 1) { auto [u, v, x] = edge[i]; et.link(u, n + i); et.link(v, n + i); } int q; cin >> q; while (q--) { int t, x; cin >> t >> x; --x; if (t == 1) { if (et.same(x, 0)) { et.cut(par[x], par[par[x]]); } } else { if (!et.same(x, 0)) { co(0); } else { co(et.get_subtree(x, par[x])); } } } } int main(void) { int t = 1; // std::cin >> t; while (t--) solve(); return 0; }