https://www.cnblogs.com/Grice/p/14263953.html
https://www.cnblogs.com/hydd-233/p/13504049.html
刚开始审错了inf次题目， (a)表示连通块(C)中被包含在集合(S)内的结点数，不包含在(S)内的点权值为0。我果然是sb。。
只写了(O(qlog^2n))的做法。
大概思路是每次调整直到(a geq b)为止。然后线段树每个点维护mn,mx分别是选入联通块的min 未选入联通块的max。
注意不在(S)内的点初始时设为(mx=-inf,mn=inf)避免它们产生影响。
对于加入操作，要通过交换点使得(mn geq mx)，然后还要决定是否新加入一个点。
对于删除操作，看这个点是否在集合内，若在需要消除它对答案的影响，不在也要试探着弹出(mn)最小的点。
我好菜啊。。还是最好看别人的博客吧。
//https://www.luogu.com.cn/blog/Mrsrz/WC2020-tree
//O(qlog^2n)
#include<bits/stdc++.h>
using namespace std;
#define fp(i,l,r) for(register int (i)=(l);(i)<=(r);++(i))
#define fd(i,l,r) for(register int (i)=(l);(i)>=(r);--(i))
#define fe(i,u) for(register int (i)=front[(u)];(i);(i)=e[(i)].next)
#define mem(a) memset((a),0,sizeof (a))
#define O(x) cerr<<#x<<':'<<x<<endl
#define lson o<<1
#define rson o<<1|1
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
void wr(int x){
if(x<0)putchar('-'),x=-x;
if(x>=10)wr(x/10);
putchar('0'+x%10);
}
const int MAXN=5e5+10,inf=1e9;
struct tEdge{
int v,next;
}e[MAXN<<1];
int front[MAXN],tcnt,hson[MAXN],top[MAXN],sze[MAXN],fa[MAXN],dep[MAXN],dfn[MAXN],idfn[MAXN],dfc,n,Q;
bool vis[MAXN];//是否加入了联通块
inline void adde(int u,int v){
e[++tcnt]={v,front[u]};front[u]=tcnt;
}
void dfs1(int u,int f,int D){
dep[u]=D;fa[u]=f;sze[u]=1;
fe(i,u){
int v=e[i].v;if(v==f)continue;
dfs1(v,u,D+1);sze[u]+=sze[v];
if(sze[v]>sze[hson[u]])hson[u]=v;
}
}
void dfs2(int u,int Tp){
top[u]=Tp;idfn[dfn[u]=++dfc]=u;
if(hson[u])dfs2(hson[u],Tp);
fe(i,u){
int v=e[i].v;if(v==hson[u]||v==fa[u])continue;
dfs2(v,v);
}
}
int mn[MAXN<<2],mx[MAXN<<2],tag[MAXN<<2],sta[40],ans;
inline void pushup(int o){
mx[o]=max(mx[lson],mx[rson]);mn[o]=min(mn[lson],mn[rson]);
}
inline void madd(int o,int v){
mx[o]+=v;mn[o]+=v;tag[o]+=v;
}
inline void pushdown(int o){
if(!tag[o])return;
madd(lson,tag[o]);madd(rson,tag[o]);tag[o]=0;
}
void add(int o,int l,int r,int ql,int qr,int v){
if(ql<=l&&qr>=r){madd(o,v);return;}
int mid=l+r>>1;pushdown(o);
if(ql<=mid)add(lson,l,mid,ql,qr,v);
if(qr>mid)add(rson,mid+1,r,ql,qr,v);
pushup(o);
}
//mn,mx分别是选入联通块的min 未选入联通块的max
void build(int o,int l,int r){
if(l==r){mn[o]=inf;mx[o]=-inf;return;}//所有不在S集合中的点不能作贡献
int mid=l+r>>1;
build(lson,l,mid);build(rson,mid+1,r);
pushup(o);
}
inline void add(int u,int c){
while(u){
add(1,1,n,dfn[top[u]],dfn[u],c);u=fa[top[u]];
}
}
inline void flip(int p){
int o=1,l=1,r=n,top=0;vis[p]^=1;p=dfn[p];
while(l!=r){
int mid=l+r>>1;pushdown(o);sta[++top]=o;
if(p<=mid)o=lson,r=mid;
else o=rson,l=mid+1;
}
if(mn[o]>1e8)mn[o]=mx[o],mx[o]=-inf;
else mx[o]=mn[o],mn[o]=inf;
fd(i,top,1)pushup(sta[i]);
}
inline void mdy(int p,bool flag){//flag=1 -> 加入了S集合
int o=1,l=1,r=n,top=0;p=dfn[p];
while(l!=r){
int mid=l+r>>1;pushdown(o);sta[++top]=o;
if(p<=mid)o=lson,r=mid;
else o=rson,l=mid+1;
}
if(flag){
if(vis[idfn[p]])mn[o]=tag[o];else mx[o]=tag[o];
}
else{
mn[o]=inf;mx[o]=-inf;
}
fd(i,top,1)pushup(sta[i]);
}
inline int gpos(int a[]){
int o=1,l=1,r=n;
while(l!=r){
int mid=l+r>>1;pushdown(o);
if(a[o]==a[lson])r=mid,o=lson;
else l=mid+1,o=rson;
}
return idfn[l];
}
inline void adjust(){
if(ans&&mn[1]<mx[1]){
int t1=gpos(mx),t2=gpos(mn);flip(t1);flip(t2);
}
}
inline void addc(int u){
add(u,1);mdy(u,1);adjust();
if(mx[1]>ans)++ans,flip(gpos(mx));
}
inline void delc(int u){
add(u,-1);mdy(u,0);if(vis[u])vis[u]=0,--ans;
else if(ans)--ans,flip(gpos(mn));
if(mx[1]>ans)++ans,flip(gpos(mx));
}
main(){
n=read();
fp(i,1,n-1){
int x=read(),y=read();adde(x,y);adde(y,x);
}
Q=read();dfs1(1,0,1);dfs2(1,1);build(1,1,n);
while(Q--){
int op=read(),x=read();
if(op==1)addc(x);else delc(x);
wr(ans);putchar('
');
}
return 0;
}