**Lazy Proagation - Graphs,trees,Policy Based Data Structure**

HackerEarth : Mother Flippin' Tree

Author : Dnynaneshwar Ware

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
#define int long long
const int N = 1e5 + 5;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree
    <T, null_type, less<T>, rb_tree_tag, 
    tree_order_statistics_node_update>;
vector<int> v[N];
vector<int> upd[N];
vector<int> ask[N];
int val[N];
ordered_set<int> st;
set<pair<int,int>> ans;
void dfs(int u,int par)
{
    for(auto i:upd[u])st.insert(i);

    for(auto time:ask[u])
    {
        int res = val[u];
        if(st.order_of_key(time) & 1)
        res = 1 - res;
        ans.emplace(time,res);
    }
    for(auto i:v[u])
    {
        if(i!=par)
        {
            dfs(i,u);
        }
    }
    for(auto i:upd[u])st.erase(i);
}
signed main()
{
    int n;
    cin >> n;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
        
    }
    for(int i=1;i<=n;i++)cin >> val[i];
    int clk=1;
    int q;
    cin >> q;
    while(q--)
    {
        string type;
        int x;
        cin >> type >> x;
        if(type == "flip")
        upd[x].push_back(clk);
        else
        ask[x].push_back(clk);
        clk++;
    }
    dfs(1,1);
    for(auto i:ans) cout << i.second << ' ';
}