#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using Int = long long; template ostream &operator<<(ostream &os, const pair &a) { return os << "(" << a.first << ", " << a.second << ")"; }; template void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; } template bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; } template bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; } // T: monoid representing information of an interval. // T() should return the identity. // T(S s) should represent a single element of the array. // T::push(T &l, T &r) should push the lazy update. // T::merge(const T &l, const T &r) should merge two intervals. template struct SegmentTreeRange { int logN, n; vector ts; SegmentTreeRange() {} explicit SegmentTreeRange(int n_) { for (logN = 0, n = 1; n < n_; ++logN, n <<= 1) {} ts.resize(n << 1); } template explicit SegmentTreeRange(const vector &ss) { const int n_ = ss.size(); for (logN = 0, n = 1; n < n_; ++logN, n <<= 1) {} ts.resize(n << 1); for (int i = 0; i < n_; ++i) at(i) = T(ss[i]); build(); } T &at(int i) { return ts[n + i]; } void build() { for (int u = n; --u; ) merge(u); } inline void push(int u) { ts[u].push(ts[u << 1], ts[u << 1 | 1]); } inline void merge(int u) { ts[u].merge(ts[u << 1], ts[u << 1 | 1]); } // Applies T::f(args...) to [a, b). template void ch(int a, int b, F f, Args &&... args) { assert(0 <= a); assert(a <= b); assert(b <= n); if (a == b) return; a += n; b += n; for (int h = logN; h; --h) { const int aa = a >> h, bb = b >> h; if (aa == bb) { if ((aa << h) != a || (bb << h) != b) push(aa); } else { if ((aa << h) != a) push(aa); if ((bb << h) != b) push(bb); } } for (int aa = a, bb = b; aa < bb; aa >>= 1, bb >>= 1) { if (aa & 1) (ts[aa++].*f)(args...); if (bb & 1) (ts[--bb].*f)(args...); } for (int h = 1; h <= logN; ++h) { const int aa = a >> h, bb = b >> h; if (aa == bb) { if ((aa << h) != a || (bb << h) != b) merge(aa); } else { if ((aa << h) != a) merge(aa); if ((bb << h) != b) merge(bb); } } } // Calculates the product for [a, b). T get(int a, int b) { assert(0 <= a); assert(a <= b); assert(b <= n); if (a == b) return T(); a += n; b += n; for (int h = logN; h; --h) { const int aa = a >> h, bb = b >> h; if (aa == bb) { if ((aa << h) != a || (bb << h) != b) push(aa); } else { if ((aa << h) != a) push(aa); if ((bb << h) != b) push(bb); } } T prodL, prodR, t; for (int aa = a, bb = b; aa < bb; aa >>= 1, bb >>= 1) { if (aa & 1) { t.merge(prodL, ts[aa++]); prodL = t; } if (bb & 1) { t.merge(ts[--bb], prodR); prodR = t; } } t.merge(prodL, prodR); return t; } // Calculates T::f(args...) of a monoid type for [a, b). // op(-, -) should calculate the product. // e() should return the identity. template #if __cplusplus >= 201402L auto #else decltype((std::declval().*F())()) #endif get(int a, int b, Op op, E e, F f, Args &&... args) { assert(0 <= a); assert(a <= b); assert(b <= n); if (a == b) return e(); a += n; b += n; for (int h = logN; h; --h) { const int aa = a >> h, bb = b >> h; if (aa == bb) { if ((aa << h) != a || (bb << h) != b) push(aa); } else { if ((aa << h) != a) push(aa); if ((bb << h) != b) push(bb); } } auto prodL = e(), prodR = e(); for (int aa = a, bb = b; aa < bb; aa >>= 1, bb >>= 1) { if (aa & 1) prodL = op(prodL, (ts[aa++].*f)(args...)); if (bb & 1) prodR = op((ts[--bb].*f)(args...), prodR); } return op(prodL, prodR); } // Find min b s.t. T::f(args...) returns true, // when called for the partition of [a, b) from left to right. // Returns n + 1 if there is no such b. template int findRight(int a, F f, Args &&... args) { assert(0 <= a); assert(a <= n); if ((T().*f)(args...)) return a; if (a == n) return n + 1; a += n; for (int h = logN; h; --h) push(a >> h); for (; ; a >>= 1) if (a & 1) { if ((ts[a].*f)(args...)) { for (; a < n; ) { push(a); if (!(ts[a <<= 1].*f)(args...)) ++a; } return a - n + 1; } ++a; if (!(a & (a - 1))) return n + 1; } } // Find max a s.t. T::f(args...) returns true, // when called for the partition of [a, b) from right to left. // Returns -1 if there is no such a. template int findLeft(int b, F f, Args &&... args) { assert(0 <= b); assert(b <= n); if ((T().*f)(args...)) return b; if (b == 0) return -1; b += n; for (int h = logN; h; --h) push((b - 1) >> h); for (; ; b >>= 1) if ((b & 1) || b == 2) { if ((ts[b - 1].*f)(args...)) { for (; b <= n; ) { push(b - 1); if (!(ts[(b <<= 1) - 1].*f)(args...)) --b; } return b - n - 1; } --b; if (!(b & (b - 1))) return -1; } } }; //////////////////////////////////////////////////////////////////////////////// struct Node { Int sum; bool lz; Node() : sum(0), lz(false) {} Node(Int val) : sum(val), lz(false) {} void push(Node &l, Node &r) { if (lz) { l.zero(); r.zero(); } lz = false; } void merge(const Node &l, const Node &r) { sum = l.sum ^ r.sum; } void zero() { sum = 0; lz = true; } }; int N; vector A, B; vector C; vector> G; vector par, dis, fin; vector is; void dfs(int u, int p) { par[u] = p; dis[u] = is.size(); for (const int i : G[u]) { const int v = A[i] ^ B[i] ^ u; if (v != p) { is.push_back(i); dfs(v, u); // is.push_back(i); } } fin[u] = is.size(); } int main() { for (; ~scanf("%d", &N); ) { A.resize(N - 1); B.resize(N - 1); C.resize(N - 1); for (int i = 0; i < N - 1; ++i) { scanf("%d%d%lld", &A[i], &B[i], &C[i]); --A[i]; --B[i]; } G.assign(N, {}); for (int i = 0; i < N - 1; ++i) { G[A[i]].push_back(i); G[B[i]].push_back(i); } par.resize(N); dis.resize(N); fin.resize(N); is.clear(); dfs(0, -1); SegmentTreeRange seg(N - 1); for (int j = 0; j < N - 1; ++j) { seg.at(j) = Node(C[is[j]]); } seg.build(); int Q; scanf("%d", &Q); for (; Q--; ) { int t, x; scanf("%d%d", &t, &x); --x; if (t == 1) { seg.ch(dis[x] - 1, fin[x], &Node::zero); } else { const Node res = seg.get(dis[x], fin[x]); printf("%lld\n", res.sum); } } #ifdef LOCAL cerr<<"========"<