D. Water in Tree

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
vector<int> g[100005];
vector<int> st;
int cnt[100005];
void dfs(int u,int par){
    cnt[u]=1;
    for(int v:g[u]){
        if(v==par) continue;
        dfs(v,u);
        cnt[u]+=cnt[v];
    }
    st.pb(u);
}
int main(){
    int t,n,x,y;
    //cin>>t;
    scanf("%d",&t);
    for(int cs=1;cs<=t;cs++){
        //cin>>n;
        scanf("%d",&n);
        for(int i=1;i<n;i++){
            //cin>>x>>y;
            scanf("%d %d",&x,&y);
            g[x].pb(y);
            g[y].pb(x);
        }
        for(int i=1;i<=n;i++){
            sort(g[i].begin(),g[i].end());
        }
        dfs(1,-1);
        int idx[n+4]={0},idx1[n+4]={0};
        for(int i=0;i<st.size();i++){
            idx[st[i]]=i+1;
            idx1[i+1]=st[i];
        }
        int q;
        //cin>>q;
        scanf("%d",&q);
        int ans[n+3]={0};
        set<int> s;
        for(int i=1;i<=n;i++) s.insert(i);
        //cout<<"Case "<<cs<<":"<<endl;
        printf("Case %d:\n",cs);
        while(q--){
            int c;
            //cin>>c;
            scanf("%d",&c);
            if(c==1){
                //cin>>x>>y;
                scanf("%d %d",&x,&y);
                int id=idx[x]-cnt[x]+1;
                if(s.size()){
                    auto lb=s.lower_bound(id);
                    int mxadd=min(idx[x]-(*lb)+1,y);
                    if(mxadd>0){
                        ll cnt1=0;

                        //cout<<"set ";
                        //for(auto it:s) cout<<it<<" "; cout<<endl;
                        vector<int> temp;
                        for(auto it=lb;it!=s.end();it++){
                            int val=*it;
                            //cout<<val<<" "<<idx[x]<<" "<<cnt1<<" "<<mxadd<<endl;
                            if(val>idx[x] || cnt1>=mxadd){
                                break;
                            }
                            cnt1++;
                            temp.pb(val); //cout<<"erased "<<val<<" node "<<idx1[val]<<endl;
                            ans[idx1[val]]=1;
                        }
                        for(int it:temp){
                            s.erase(it);
                        }
                    }
                }
            }
            else{
                //cin>>x;
                scanf("%d",&x);
                cout<<ans[x]<<endl;
            }
        }
        for(int i=1;i<=n;i++){
            g[i].clear();
            cnt[i]=0;
        }
        st.clear();
    }
    return 0;
}