#line 2 "cpplib/util/template.hpp" #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx2") #include using namespace std; struct __INIT__{__INIT__(){cin.tie(0);ios::sync_with_stdio(false);cout< vec; typedef vector> mat; typedef vector>> mat3; typedef vector svec; typedef vector> smat; templateusing V=vector; templateusing VV=V>; templateinline void output(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<inline void output2(T t){for(auto i:t)output(i);} templateinline void debug(T t){bool f=0;for(auto i:t){cerr<<(f?" ":"")<inline void debug2(T t){for(auto i:t)debug(i);} #define loop(n) for(long long _=0;_<(long long)(n);++_) #define _overload4(_1,_2,_3,_4,name,...) name #define __rep(i,a) repi(i,0,a,1) #define _rep(i,a,b) repi(i,a,b,1) #define repi(i,a,b,c) for(long long i=(long long)(a);i<(long long)(b);i+=c) #define rep(...) _overload4(__VA_ARGS__,repi,_rep,__rep)(__VA_ARGS__) #define _overload3_rev(_1,_2,_3,name,...) name #define _rep_rev(i,a) repi_rev(i,0,a) #define repi_rev(i,a,b) for(long long i=(long long)(b)-1;i>=(long long)(a);--i) #define rrep(...) _overload3_rev(__VA_ARGS__,repi_rev,_rep_rev)(__VA_ARGS__) // #define rep(i,...) for(auto i:range(__VA_ARGS__)) // #define rrep(i,...) for(auto i:reversed(range(__VA_ARGS__))) // #define repi(i,a,b) for(lint i=lint(a);i<(lint)(b);++i) // #define rrepi(i,a,b) for(lint i=lint(b)-1;i>=lint(a);--i) // #define irep(i) for(lint i=0;;++i) // inline vector range(long long n){if(n<=0)return vector();vectorv(n);iota(v.begin(),v.end(),0LL);return v;} // inline vector range(long long a,long long b){if(b<=a)return vector();vectorv(b-a);iota(v.begin(),v.end(),a);return v;} // inline vector range(long long a,long long b,long long c){if((b-a+c-1)/c<=0)return vector();vectorv((b-a+c-1)/c);for(int i=0;i<(int)v.size();++i)v[i]=i?v[i-1]+c:a;return v;} // templateinline T reversed(T v){reverse(v.begin(),v.end());return v;} #define all(n) begin(n),end(n) templatebool chmin(T& s,const E& t){bool res=s>t;s=min(s,t);return res;} templatebool chmax(T& s,const E& t){bool res=s(s,t);return res;} const string ds="DRUL"; const vector dx={1,0,-1,0,1,1,-1,-1}; const vector dy={0,1,0,-1,1,-1,1,-1}; #define SUM(v) accumulate(all(v),0LL) #if __cplusplus>=201703L templateauto make_vector(T x,int arg,Args ...args){if constexpr(sizeof...(args)==0)return vector(arg,x);else return vector(arg,make_vector(x,args...));} #endif #define extrep(v,...) for(auto v:__MAKE_MAT__({__VA_ARGS__})) #define bit(n,a) ((n>>a)&1) vector> __MAKE_MAT__(vector v){if(v.empty())return vector>(1,vector());long long n=v.back();v.pop_back();vector> ret;vector> tmp=__MAKE_MAT__(v);for(auto e:tmp)for(long long i=0;i>; templateusing graph_w=vector>>; templateostream& operator<<(ostream& out,pairv){out<<"("<=201703L constexpr inline long long powll(long long a,long long b){long long res=1;while(b--)res*=a;return res;} #endif templatepair& operator+=(pair&s,const pair&t){s.first+=t.first;s.second+=t.second;return s;} templatepair& operator-=(pair&s,const pair&t){s.first-=t.first;s.second-=t.second;return s;} templatepair operator+(const pair&s,const pair&t){auto res=s;return res+=t;} templatepair operator-(const pair&s,const pair&t){auto res=s;return res-=t;} // 128*1024*1024 #define BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024)); #define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_); #line 5 "cpplib/graph_tree/graph_template.hpp" /** * @brief グラフテンプレート */ using graph=std::vector>; template using graph_w=std::vector>>; graph load_graph(int n,int m){graph g(n);for(int i=0;i>s>>t;--s;--t;g[s].push_back(t);g[t].push_back(s);}return g;} graph load_digraph(int n,int m){graph g(n);for(int i=0;i>s>>t;--s;--t;g[s].push_back(t);}return g;} graph load_graph0(int n,int m){graph g(n);for(int i=0;i>s>>t;g[s].push_back(t);g[t].push_back(s);}return g;} graph load_digraph0(int n,int m){graph g(n);for(int i=0;i>s>>t;g[s].push_back(t);}return g;} graph load_tree(int n){graph g(n);for(int i=0;i>s>>t;--s;--t;g[s].push_back(t);g[t].push_back(s);}return g;} graph load_tree0(int n){graph g(n);for(int i=0;i>s>>t;g[s].push_back(t);g[t].push_back(s);}return g;} graph load_treep(int n){graph g(n);for(int i=0;i>t;g[i+1].push_back(t);g[t].push_back(i+1);}return g;} templategraph_w load_graph_weight(int n,int m){graph_w g(n);for(int i=0;i>s>>t>>u;--s;--t;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;} templategraph_w load_digraph_weight(int n,int m){graph_w g(n);for(int i=0;i>s>>t>>u;--s;--t;g[s].emplace_back(t,u);}return g;} templategraph_w load_graph0_weight(int n,int m){graph_w g(n);for(int i=0;i>s>>t>>u;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;} templategraph_w load_digraph0_weight(int n,int m){graph_w g(n);for(int i=0;i>s>>t>>u;g[s].emplace_back(t,u);}return g;} templategraph_w load_tree_weight(int n){graph_w g(n);for(int i=0;i>s>>t>>u;--s;--t;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;} templategraph_w load_tree0_weight(int n){graph_w g(n);for(int i=0;i>s>>t>>u;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;} templategraph_w load_treep_weight(int n){graph_w g(n);for(int i=0;i>t>>u;g[i+1].emplace_back(t,u);g[t].emplace_back(i+1,u);}return g;} #line 3 "cpplib/alga/maybe.hpp" /** * @brief Maybe * @see https://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%8A%E3%83%89_(%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0)#Maybe%E3%83%A2%E3%83%8A%E3%83%89 */ template struct maybe{ bool _is_none; T val; maybe():_is_none(true){} maybe(T val):_is_none(false),val(val){} T unwrap()const{ assert(!_is_none); return val; } T unwrap_or(T e)const{ return _is_none?e:val; } bool is_none()const{return _is_none;} bool is_some()const{return !_is_none;} }; template auto expand(F op){ return [&op](const maybe& __s,const maybe& __t)->maybe{ if(__s.is_none())return __t; if(__t.is_none())return __s; return maybe(op(__s.unwrap(),__t.unwrap())); }; } #line 3 "cpplib/segment_tree/lazy_segment_tree.hpp" template class lazy_segment_tree{ using i64=long long; i64 n; i64 sz; struct node; using np=node*; struct node{ maybe val=maybe(); maybe lazy=maybe(); np lch=nullptr,rch=nullptr; node(){} }; np root=new node(); maybe fix(i64 a,T x,i64 l,i64 r,np t){ auto f=expand(_f); eval(t,l,r); //区間外 if(r<=a||aval; //全部区間内 if(l==a&&r==a+1){ eval(t,l,r); t->val=x; return t->val; } //一部区間内 return t->val=f(fix(a,x,l,(l+r)/2,t->lch),fix(a,x,(l+r)/2,r,t->rch)); } maybe update(i64 a,i64 b,E x,i64 l,i64 r,np t){ auto f=expand(_f); eval(t,l,r); //区間外 if(r<=a||b<=l)return t->val; //全部区間内 if(a<=l&&r<=b){ t->lazy=x; eval(t,l,r); return t->val; } //一部区間内 return t->val=f(update(a,b,x,l,(l+r)/2,t->lch),update(a,b,x,(l+r)/2,r,t->rch)); } maybe get(i64 a,i64 b,i64 l,i64 r,np t){ auto f=expand(_f); eval(t,l,r); //区間外 if(r<=a||b<=l)return maybe(); //全部区間内 if(a<=l&&r<=b)return t->val; //一部区間内 return f(get(a,b,l,(l+r)/2,t->lch),get(a,b,(l+r)/2,r,t->rch)); } void eval(np t,i64 l,i64 r){ auto g=expand(_g); if(r-l>1){ if(!t->lch)t->lch=new node(); if(!t->rch)t->rch=new node(); t->lch->lazy=g(t->lch->lazy,t->lazy); t->rch->lazy=g(t->rch->lazy,t->lazy); } t->val=h(t->val,t->lazy,l,r); t->lazy=maybe(); } template i64 lower_bound_right(maybe now,np t,Less op,i64 l,i64 r){ auto f=expand(_f); eval(t,l,r); if(t->lch)eval(t->lch,l,(l+r)/2); if(t->rch)eval(t->rch,(l+r)/2,r); const auto p=t->rch?f(t->rch->val,now):now; if(r-l==1){ return 0; } if(!op(f(t->val,now))){ return r-l; } if(op(p)){ return lower_bound_right(now,t->rch,op,(l+r)/2,r); }else{ return (r-l)/2+lower_bound_right(p,t->lch,op,l,(l+r)/2); } } F _f;G _g;H _h; maybe h(const maybe&s,const maybe&t,i64 l,i64 r){ if(t.is_none())return s; else return maybe(_h(s,t.unwrap(),l,r)); } public: lazy_segment_tree(i64 sz,F f=F(),G g=G(),H h=H()):n(1),sz(sz),_f(f),_g(g),_h(h){while(n get(i64 a,i64 b){return get(a,b,0,n,root);} template i64 lower_bound_right(Less op){ return n-lower_bound_right(maybe(),root,op,0,n); } }; #line 4 "cpplib/graph_tree/HLD_lazy.hpp" template struct HLD_lazy{ int child_size(const graph& v,int n,int p){ int cnt=0; for(auto t:v[n]){ if(t!=p)cnt+=child_size(v,t,n); } return sz[n]=cnt+1; } void make(const graph& v,int root){ sz=new int[v.size()]; vertex=new int[v.size()]; par=new int[v.size()]; head=new int[v.size()]; child_size(v,root,-1); stack>stk; stk.emplace(root,-1); int idx=0; par[root]=root; head[root]=root; while(!stk.empty()){ int n,p; tie(n,p)=stk.top(); stk.pop(); vertex[n]=idx++; int mx=0,heavy=-1; for(auto t:v[n])if(t!=p&&mx* seg; public: HLD_lazy(const graph& v,int root=0,F f=F(),G g=G(),H h=H()):_f(f),_g(g),_h(h){ make(v,root); seg=new lazy_segment_tree(v.size(),f,g,h); } // HLD_lazy(const graph& v,const vector& a,int root=0,F f=F(),G g=G(),H h=H()):_f(f),_g(g),_h(h){ // vectortmp(v.size()); // make(v,root); // for(int i=0;i<(int)v.size();i++){ // tmp[vertex[i]]=a[i]; // } // seg=new lazy_segment_tree(tmp,f,g,h); // } int lca(int l,int r){ while(1){ if(head[l]==head[r])return sz[l]>sz[r]?l:r; else if(sz[head[l]]>sz[head[r]])r=par[r]; else l=par[l]; } } inline void fix_vertex(int u,T x){ seg->fix(vertex[u],x); } inline void update_vertex(int u,E x){ seg->update(vertex[u],vertex[u]+1,x); } inline maybe get_vertex(int u){ return seg->get(vertex[u],vertex[u]+1); } inline void update_subtree(int u,E x){ seg->update(vertex[u],vertex[u]+sz[u],x); } inline maybe get_subtree(int u){ return seg->get(vertex[u],vertex[u]+sz[u]); } void update_path(int u,int v,E x){ while(1){ if(head[u]==head[v]){ seg->update(vertex[u],vertex[v],x); break; } else if(sz[head[u]]>sz[head[v]]){ seg->update(vertex[v],vertex[head[v]],x); v=par[v]; } else{ seg->update(vertex[u],vertex[head[u]],x); u=par[u]; } } } T get_path(int u,int v){ auto f=expand(_f); maybe res; while(1){ if(head[u]==head[v]){ return f(res,seg->get(vertex[u],vertex[v])); } else if(sz[head[u]]>sz[head[v]]){ res=f(res,seg->get(vertex[v],vertex[head[v]])); v=par[v]; } else{ res=f(res,seg->get(vertex[u],vertex[head[u]])); u=par[u]; } } } }; #line 3 "cpplib/segment_tree/dual_segment_tree.hpp" /** * @brief 双対セグメント木 */ template class dual_segment_tree{ struct node; using np=node*; using i64=long long; struct node{ maybe val; np ch[2]={nullptr,nullptr}; node(maybe val=maybe()):val(val){} }; np root=nullptr; i64 n=1,sz; F op; public: dual_segment_tree(i64 sz,F op=F()):sz(sz),op(op){while(n get(i64 x){return get(x,0,n,root);} private: void eval(np& t){ auto f=expand(op); if(t->val.is_none())return; if(!t->ch[0])t->ch[0]=new node(); if(!t->ch[1])t->ch[1]=new node(); t->ch[0]->val=f(t->ch[0]->val,t->val); t->ch[1]->val=f(t->ch[1]->val,t->val); t->val=maybe(); } void fix(i64 a,T x,i64 l,i64 r,np& t){ if(!t)t=new node(); if(r-l>1)eval(t); if(r<=a||aval=x; else if(r-l>1){ fix(a,x,l,(l+r)/2,t->ch[0]); fix(a,x,(l+r)/2,r,t->ch[1]); } } void update(i64 a,i64 b,T x,i64 l,i64 r,np& t){ auto f=expand(op); if(!t)t=new node(); if(r-l>1)eval(t); if(r<=a||b<=l)return; else if(a<=l&&r<=b)t->val=f(t->val,x); else if(r-l>1){ update(a,b,x,l,(l+r)/2,t->ch[0]); update(a,b,x,(l+r)/2,r,t->ch[1]); } } maybe get(i64 x,i64 l,i64 r,np& t){ auto f=expand(op); if(!t)t=new node(); if(r-l>1)eval(t); if(x(); else if(r-l==1){ return t->val; } else return f(get(x,l,(l+r)/2,t->ch[0]),get(x,(l+r)/2,r,t->ch[1])); } }; #line 4 "main.cpp" int main(){ auto f=[&](auto s,auto t){ return s^t; }; auto g=[&](auto s,auto t){ return s||t; }; auto h=[&](auto s,auto t,auto l,auto r)->lint{ if(t)return 0; return s.unwrap_or(0); }; lint n; cin>>n; vector>>gg(n); graph v(n); rep(i,n-1){ lint s,t,u; cin>>s>>t>>u; s--;t--; gg[s].emplace_back(t,u); gg[t].emplace_back(s,u); v[s].emplace_back(t); v[t].emplace_back(s); } vec cnt(n),pp(n),cnt2(n); auto dfs=[&](auto dfs,lint now,lint p)->void{ for(auto [e,c]:gg[now]){ if(e==p)continue; cnt[now]^=c; cnt2[e]=c; pp[e]=now; dfs(dfs,e,now); } }; auto f2=[&](auto s,auto t){ return s&&t; }; dfs(dfs,0,-1); HLD_lazyhld(v,0,f,g,h); dual_segment_treest(n,f2); rep(i,n){ hld.fix_vertex(i,cnt[i]); } lint q; cin>>q; rep(i,n)st.fix(i,1); while(q--){ lint t,x; cin>>t>>x; x--; if(t==1){ bool b=st.get(hld.vertex[x]).unwrap_or(0); hld.update_subtree(x,1); st.update(hld.vertex[x],hld.vertex[x]+hld.sz[x],0); if(pp[x]!=-1&&b){ hld.fix_vertex(pp[x],hld.get_vertex(pp[x]).unwrap_or(0)^cnt2[x]); } }else{ cout<get(hld.vertex[x]+1,hld.vertex[x]+hld.sz[x]).unwrap_or(0)<