#include "nuclear.h"
#include <vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define NN 200005
#define lc(x) t[x].ch[0]
#define rc(x) t[x].ch[1]
#define fa(x) t[x].fa
#define va(x) t[x].va
#define su(x) t[x].su
#define sv(x) t[x].sv
#define ta(x) t[x].ta
#define db double
#define ul unsigned long long
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define rf(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
int n,m,k,h[NN],cnt,op,ans,x,y,z;
struct node{int ch[2],fa,va,su,sv;bool ta;}t[NN];
void swap(int &x,int &y){int t=x;x=y;y=t;}
struct edge{int v,n;}e[NN<<1];
void ad(int u,int v){e[++cnt]={v,h[u]};h[u]=cnt;}
void pu(int x){su(x)=su(lc(x))+su(rc(x))+sv(x)+va(x);}
void rv(int x){swap(lc(x),rc(x));ta(x)^=1;}
void pd(int x){
    if(ta(x)){
        rv(lc(x));
        rv(rc(x));
        ta(x)=0;
    }
}
bool nt(int x){int y=fa(x);return lc(y)==x||rc(y)==x;}
void push(int x){
    if(nt(x))push(fa(x));
    pd(x);
}
void ro(int x){
    int y=fa(x),g=fa(y),k=rc(y)==x;
    if(nt(y))t[g].ch[rc(g)==y]=x;
    fa(x)=g;
    if(t[x].ch[k^1])fa(t[x].ch[k^1])=y;
    t[y].ch[k]=t[x].ch[k^1];
    fa(y)=x;t[x].ch[k^1]=y;
    pu(y);pu(x);
}
void splay(int x){
    push(x);
    for(;nt(x);ro(x)){
        int y=fa(x),g=fa(y);
        if(nt(y))ro((rc(y)==x)^(rc(g)==y)?x:y);
    }
}
void access(int x){
    for(int y=0;x;y=x,x=fa(x)){
        splay(x);
        sv(x)+=su(rc(x));
        rc(x)=y;
        sv(x)-=su(y);
        pu(x);
    }
}
void makeroot(int x){
    access(x);splay(x);rv(x);
}
int find(int x){
    access(x);splay(x);pd(x);
    while(lc(x))x=lc(x),pd(x);
    splay(x);
    return x;
}
void link(int x,int y){
    makeroot(x);makeroot(y);
    fa(x)=y;sv(y)+=su(x);pu(y);
}
bool cut(int x,int y){
    makeroot(x);
    if(find(y)==x&&rc(x)==y&&!lc(y)){
        rc(x)=fa(y)=0;
        pu(x);
        return 1;
    }
    return 0;
}
void initialize(int N, std::vector<int> A, std::vector<int> B){
	n=N;
	fo(i,0,n-2){
	    ad(A[i]+1,B[i]+1);
	    ad(B[i]+1,A[i]+1);
	    link(A[i]+1,B[i]+1);
    }
}
 
int generate(int v, bool result){
    v++;
	makeroot(v);
	ans-=su(v)>>1;
	if(result){
	    va(v)=1;pu(v);
	    ans+=su(v)>>1;
	    return ans;
    }
	for(int i=h[v];i;i=e[i].n){
	    int y=e[i].v;
	    if(cut(v,y)){
	        makeroot(y);
	        ans+=su(y)>>1;
        }
    }
	return ans;
}