#include <bits/stdc++.h>
#include "nuclear.h" 
using namespace std;
const int N=2e5+10;
vector<int>G[N];
int siz[N],Fa[N],de[N],son[N],n;
int top[N],dfn[N],cnt,tmp,ans;
int mk[N],val[N],del[N];
void add(int x,int y){
    G[x].push_back(y);
}
struct node{
    int d,x;
    bool operator < (const node &u)const{
        return d<u.d;
    }
};
set<node>st[N];
void dfs1(int x,int fa){
    siz[x]=1,Fa[x]=fa;
    de[x]=de[fa]+1;
    for(auto y:G[x]){
        if(y==fa)continue;
        dfs1(y,x);
        siz[x]+=siz[y];
        if(siz[y]>siz[son[x]]){
            son[x]=y;
        }
    }
    return;
}
void dfs2(int x,int tp){
    top[x]=tp,dfn[x]=++cnt;
    if(!son[x])return;
    dfs2(son[x],tp);
    for(auto y:G[x]){
        if(y==Fa[x]||y==son[x])continue;
        dfs2(y,y);
    }
    return;
}
int found(int x){
    while(1){
        int tp=top[x];
        if(st[tp].size()){
            auto it=st[tp].upper_bound(node{de[x],0});
            if(it!=st[tp].begin()){
                --it;
                return (*it).x;
            }
        }
        x=Fa[tp];
    }
    return 1;
}
struct sgt{
    int tag[N<<2];
    #define ls (p<<1)
    #define rs (p<<1|1)
    void add(int p,int l,int r,int L,int R,int v){
        if(L<=l&&r<=R){
            tag[p]+=v;
        }else{
            int mid=(l+r)>>1;
            if(L<=mid)add(ls,l,mid,L,R,v);
            if(R>mid)add(rs,mid+1,r,L,R,v);
        }
    }
    int ask(int p,int l,int r,int x){
        if(l==r)return tag[p];int mid=(l+r)>>1;
        if(x<=mid)return ask(ls,l,mid,x)+tag[p];
        if(x>mid)return ask(rs,mid+1,r,x)+tag[p];
    }
}tr;
void upd(int a,int b,int c){
    while(top[a]!=top[b]){
        tr.add(1,1,n,dfn[top[a]],dfn[a],c);
        a=Fa[top[a]];
    }
    tr.add(1,1,n,dfn[b],dfn[a],c);
    return;
} 
int ask(int u){
    return tr.ask(1,1,n,dfn[u]);   
}
void initialize(int N, std::vector<int> A, std::vector<int> B){
    n=N;
    for(int i=0;i<n-1;i++){
        A[i]++,B[i]++;
        add(A[i],B[i]),add(B[i],A[i]);
    } 
    dfs1(1,0);
    dfs2(1,1);
    st[1].insert(node{1,1});
    mk[1]=1;
}
int generate(int u, bool result){
    u++;int x=result;
    if(x==1){
        int rot=found(u);
        tmp=ask(rot);
        ans-=tmp/2;
        upd(u,rot,1);
        tmp=ask(rot);
        ans+=tmp/2;
    }else{
        del[u]=1;
        int rot=found(u);
        int sz=ask(u);
        tmp=ask(rot);
        ans-=tmp/2;
        if(u!=rot){   
            upd(Fa[u],rot,-sz);
            tmp=ask(rot);
            ans+=tmp/2;
        }else{
            st[top[u]].erase(node{de[u],u});
        }
        for(auto v:G[u]){
            if(v==Fa[u])continue;
            if(del[v])continue;
            st[top[v]].insert(node{de[v],v});
            tmp=ask(v);
            ans+=tmp/2;
            mk[v]=1;
        }
    }
    return ans;
}