# HackerEarth Tree query problem solution

In this HackerEarth Tree query problem solution, A tree is a simple graph in which every two vertices are connected by exactly one path. You are given a rooted tree with n vertices and a lamp is placed on each vertex of the tree.

You are given  queries of the following two types:
1. v: You switch the lamp placed on the vertex v, that is, either from On to Off or Off to On.
2. v: Determine the number of vertices connected to the subtree of v if you only consider the lamps that are in On state. In other words, determine the number of vertices in the subtree of v, such as u, that can reach from u by using only the vertices that have lamps in the On state.

## HackerEarth Tree query problem solution.

`#include<bits/stdc++.h>using namespace std;#define ll long long#define pb push_backconst int maxn = 5e5 + 20;vector<int> adj[maxn];int st[maxn] , ft[maxn] , now = -1 , is[maxn];void dfs(int v , int p = -1){    st[v] = ++now;    for(auto u : adj[v])        if(u != p)            dfs(u , v);        ft[v] = now + 1;}int mn[maxn * 4] , t[maxn * 4] , Add[maxn * 4] , n;void build(int s = 0 , int e = n , int v = 1){    t[v] = e - s;    if(e - s < 2)        return;        int m = (s + e) / 2;    build(s , m , 2 * v);    build(m , e , 2 * v + 1);}void add(int l , int r , int val , int s = 0 , int e = n , int v = 1){    if(l <= s && e <= r)    {        mn[v] += val;        Add[v] += val;        return;    }    if(r <= s || e <= l)        return;    int m = (s + e) / 2;    add(l , r , val , s , m , 2 * v);    add(l , r , val , m , e , 2 * v + 1);    mn[v] = min(mn[2 * v] , mn[2 * v + 1]);    t[v] = 0;    if(mn[v] == mn[2 * v])        t[v] += t[2 * v];    if(mn[v] == mn[2 * v + 1])        t[v] += t[2 * v + 1];    mn[v] += Add[v];}pair<int , int> get(int l , int r , int s = 0 , int e = n , int v = 1){    if(l <= s && e <= r)        return make_pair(mn[v] , t[v]);    if(r <= s || e <= l)        return make_pair(1e9 , 0);        int m = (s + e) / 2;    auto x = get(l , r , s , m , 2 * v);    auto y = get(l , r , m , e , 2 * v + 1);    pair<int , int> ans = {1e9 , 0};    ans.first = min(x.first , y.first);    if(ans.first == x.first)        ans.second += x.second;    if(ans.first == y.first)        ans.second += y.second;    ans.first += Add[v];    return ans;}int main(){    int q;    scanf("%d%d", &n, &q);    for(int i = 0; i < n - 1; i++)    {        int a , b;        scanf("%d%d", &a, &b);        a-- , b--;        adj[a].pb(b);        adj[b].pb(a);    }    dfs(0);    build();    while(q--)    {        int type , v;        cin >> type >> v;        v--;        if(type == 1)        {            add(st[v] , ft[v] , is[v]? -1 : 1);            is[v] ^= 1;        }        else        {            if(is[v])                printf("0\n");            else                printf("%d\n", get(st[v] , ft[v]).second);         }    }}`

### Second solution

`#include <bits/stdc++.h>using namespace std; typedef long long ll;const int maxn = 5e5 + 14;int n, q;struct node{    int m,n;}  s[maxn<<2], emp={1717171717,0};node operator &(const node &a,const node &b){    if(a.m<b.m)return a;    if(b.m<a.m)return b;    return {a.m,a.n+b.n};}vector<int>g[maxn];int st[maxn],en[maxn],Time,lazy[maxn<<2];void shift(int id){    if(!lazy[id])return;    lazy[id<<1]+=lazy[id],lazy[id<<1|1]+=lazy[id];    s[id<<1].m+=lazy[id];    s[id<<1|1].m+=lazy[id];      lazy[id]=0;}node get(int st,int en,int l=0,int r=n,int id=1){    if(en<=l || r<=st)return emp;    if(st<=l && r<=en)return s[id];    shift(id);    int mid=(l+r)>>1;    return get(st,en,l,mid,id<<1)&get(st,en,mid,r,id<<1|1);}void add(int st,int en,int v=1,int l=0,int r=n,int id=1){    if(en<=l || r<=st)return;    if(st<=l && r<=en){        s[id].m+=v;        lazy[id]+=v;        return;    }    shift(id);    int mid=(l+r)>>1;    add(st,en,v,l,mid,id<<1);    add(st,en,v,mid,r,id<<1|1);    s[id]=s[id<<1]&s[id<<1|1];}void build(int l=0,int r=n,int id=1){    s[id].n=r-l;    int mid=(l+r)>>1;    if(r-l>1)        build(l,mid,id<<1),build(mid,r,id<<1|1);}void sten(int v=0,int p=-1){    st[v]=Time++;    for(auto &u:g[v])        if(u!=p)            sten(u,v);    en[v]=Time;}void addVer(int v, int x){    add(st[v], en[v], x);}bool state[maxn];int main(){    ios::sync_with_stdio(0), cin.tie(0);    cin >> n >> q;    for(int i = 1; i < n; i++){        int v, u;        cin >> v >> u;        v--, u--;        g[v].push_back(u);        g[u].push_back(v);    }    sten();    build();    while(q--){        int t, v;        cin >> t >> v;        v--;        if(t == 1)            addVer(v, (state[v] ^= 1) ? +1 : -1);        else            cout << !state[v] * get(st[v], en[v]).n << '\n';    }}`