[WC 2020] 뿌리 나무 (경중 체인 분할)

제목.
문제 에 11, 1 이 포 함 된 연결 블록 은 당신 을 제시 하 는 것 이지 당신 을 제한 하 는 것 이 아니 라 는 것 을 쉽게 발견 할 수 있 습 니 다.그러면 정 답 은 반드시 S S S 에서 가장 큰 몇 개의 w w 를 선택 하고 나머지 w w w 의 최대 치 ≤ 8739 ° S 8739 ° S 8739 ° \ leq | S | ≤ 8739 ° S 8739 ° 이다.남 은 w w w 를 집합 X X X 로 설정 하여 조정 하 는 과정 을 고려 합 니 다.{w \ in X} w 8739 ° S 8739 ° S * 8739 ° < maxw * 8712 ° X w, max * 8289 ° w * 8712 ° X w \ max{w \ in X} w maxw 8712 ° X w X X X 에서 삭제 한 후 S S S 를 추가 합 니 다.8739 ° S * 8739 ° S > max * 8289 ° w * 8712 ° X w | S | \ \ lt \ max{w \ in X} w 8739 ° S 8739 ° S > maxw 8712 ° X w 및 min * 8289 ° w 8712 ° S w ≤ max * 8289 ° w 8712 ° X w \ min{w \in S} w \leq \max_{w \ in X} w minw 8712 ° S w ≤ maxw 8712 ° X w 를 선택 하면 min * 8289 ° w 8712 ° S w \ min{w \ in S} w minw * 8712 ° S w 는 S S S 에서 삭제 한 후 X X X 를 추가 합 니 다.그리고 매번 삭제 할 때마다 한 번 만 조정 된다.(단, 전 제 는 당신 이 머리 없 이 모든 점 을 X X X 에 추가 하 는 것 이 아니 라, 현재 가입 한 점 w > max * 8289 ° w * 8712 ° X w \ \ lt \ max {w \ in X} w > maxw * 8712 ° X w 라면 S S S 를 추가 해 야 합 니 다. 그렇지 않 으 면 S S 와 X X X X 를 효율적으로 유지 할 수 없습니다.) 여기 주의 하 세 요. 우 리 는 반드시 max * 8289 ° w * 8712 ° X ≤ min * 8289 ° w * 8712 ° S \ max{w \in X} \leq \min_{w \in S} maxw∈X​≤minw∈S​。 그러면 아주 간단 한 O (q log ⁡ 2 n) O (q \ log ^ 2n) O (qlog2n) 방법 이 있 습 니 다. 선분 수 는 각 점 의 w w w 를 유지 하고 각 구간 의 max ⁡ w * 878712 ° X w, min * 8289; w * 8712 ° S w \ max{w \in X} w , \min_{w \ in S} w maxw 8712 ° X w, minw 8712 ° S w, 그리고 매번 조정 하면 됩 니 다.우 리 는 구간 추가 작업 이 있 음 을 알 게 되 었 습 니 다. 만약 에 이번 조작 후에 max * 8289 ° w * 8712 ° X ≤ min * 8289 ° w * 8712 ° S \ max 를 만족 시 키 지 못 하면{w \in X} \leq \min_{w \in S} maxw∈X​≤minw∈S​。 그러면 반드시 (최대 한 점 만 있 음) 에 1 을 더 하면 8739 ° S * 8739 ° S * 8739 ° S * 8739 ° S | + 1 * 8739 ° S * 8739 ° S * 8739 ° S * 8739 ° S | 8739 ° S * 8739 ° S * 8739 ° S * 8739 ° S * 8739 ° S * 8739 ° 의 요 소 를 발견 할 수 있 습 니 다.그러면 한 가지 점 만 규칙 에 어 긋 날 수 있 습 니 다. 우 리 는 이러한 한 쌍 을 찾 아 냈 습 니 다. 그들 은 각각 X, S X, S, S 에서 그들 을 각각 X, S X, S 에서 삭제 한 후에 각각 S, X S, X S, X 를 추가 하면 됩 니 다.구간 을 줄 이 고 독자 스스로 생각 하 세 요.z k w zkw zkw 선분 트 리 를 사용 하면 L O J LOJ LOJ 에서 이 문 제 를 걸 수 있 습 니 다.
하지만 이 문 제 는 O (n log ⁡ n) O (n \ log n) O (nlogn) 방법 도 있다.그러나 트 리 배열 의 단일 점 수정 + + 서브 트 리 는 쉽게 할 수 있 습 니 다. 다만 전체 최소 치 를 구 할 수 없습니다.문제 가 주 는 힌트 를 고려 하면 S S S 는 뿌리 를 포함 하 는 연결 블록 이 어야 합 니 다. 따라서 하나의 체인 에 있 는 모든 X X X 에 있 는 점 은 맨 위 에 있 는 점 만 max * 8289 ° w * 8712 ° X w \ max 로 자격 이 있 습 니 다.{w \ in X} w maxw 8712 ° X w 가 작 동 합 니 다.네.그러면 우 리 는 모든 체인 의 X / S X / S X / S 중 깊이 가 가장 작고 큰 점 의 w w 만 유지 합 니 다.(s e t set 로) 이 점 들 이 삭 제 됩 니 다. 가입 할 때 우 리 는 트 리 배열 O (log ⁡ n) O (\ log n) O (logn) 로 그들의 w w w 를 구 합 니 다.한 개의 체인 의 어떤 접두사 가 전체적으로 1 을 더 하거나 줄 일 때 깊이 를 통 해 X / S X / S X / S 에서 깊이 가 가장 작고 큰 점 의 w w w 가 1 을 더 하거나 줄 여야 하 는 지 판단 합 니 다.그러면 우 리 는 O (log ⁡ n) O (\ log n) O (logn) 를 삽입 할 수 있 는 것 이 필요 합 니 다. O (1) O (1) O (1) O (1) 는 점 하 나 를 찾 아 삭제 하고 그의 값 을 다시 삽입 할 수 있 습 니 다. O (log ⁡ n) O (\ log n) O (logn) 는 최대 / 최소 값 을 구 합 니 다.매번 한 번 만 조정 하 는 것 을 알 기 때문에 최대 치 / 최소 치 를 구하 면 w w 를 특정한 값 으로 구 하 는 점 으로 바 꿀 수 있 습 니 다.실제로 양 방향 링크 를 직접 작성 합 니 다.
빅 데이터 구 조 를 많이 써 서 나 는 이미 누 를 줄 모 르 는데 어 떡 하지?
A C   C o d e \mathcal AC \ Code AC Code

#include
#define maxn 500005
#define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)
#define per(i,j,k) for(int i=(j),LIM=(k);i>=LIM;i--)
#define LL long long
#define pb push_back
#define pii pair
#define vc vector
#define vi vc
#define Ct const
#define db double
using namespace std;

namespace IO{
	char cb[1<<16] , *cs=cb,*ct=cb;
	char getc(){ return cs == ct && (ct = (cs = cb) + fread(cb,1,1<<16,stdin),cs == ct) ? 0 : *cs++; }
	template<class T>void read(T &res){
		char ch;bool f=0;
		for(;!isdigit(ch=getc());) if(ch=='-') f = 1;
		for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0');
		(f) && (res = -res);
	}
};
using IO :: getc;
using IO :: read;

int n,q,ans;
vi G[maxn];
int tp[maxn],son[maxn],sz[maxn],st[maxn],ed[maxn],pos[maxn],fa[maxn],tot;
struct cmp{
	bool operator ()(Ct int &u,Ct int &v)Ct{ return st[u] < st[v]; }
};
set<int,cmp>P[maxn][2];
int W[maxn],B[maxn];

namespace BIT{
	int tr[maxn];
	void upd(int u,int v){ for(;u<=n;u+=u&-u) tr[u] += v;  }
	int qry(int u){ int r=0;for(;u;u-=u&-u) r+=tr[u]; return r; }
};
using BIT::upd;
using BIT::qry;

struct Chains{
	vi G[maxn];
	int loc[maxn];
	
	void ins(int u,int w=-1){
		if(w == -1) w = qry(ed[u]) - qry(st[u] - 1);
		loc[u] = G[w].size();
		G[w].push_back(u);
	}
	void del(int u,int w=-1){
		if(w == -1) w = qry(ed[u]) - qry(st[u] - 1);
		assert(!G[w].empty());
		int t = G[w].back();
		swap(loc[u] , loc[t]);
		swap(G[w][loc[u]] , G[w][loc[t]]);
		G[w].pop_back();
	}
}C[2];

void INS(set<int,cmp>&u,Chains &v,int t){
	if(u.empty()) return;
	int p = (t ? *u.rbegin() : *u.begin());
	v.ins(p,W[p]);
}

void DEL(set<int,cmp>&u,Chains &v,int t){
	if(u.empty()) return;
	int p = (t ? *u.rbegin() : *u.begin());
	v.del(p,W[p]);
}

void dfs0(int u,int ff){
	fa[u] = ff , sz[u] = 1;
	for(int v:G[u]) if(v^ff)
		dfs0(v,u) , sz[u] += sz[v] , (sz[v] > sz[son[u]]) && (son[u] = v);
}

void dfs1(int u,int ff){
	pos[st[u] = ++tot] = u;
	if(son[u]) tp[son[u]] = tp[u] , dfs1(son[u],u);
	for(int v:G[u]) if(v^ff && v ^ son[u])
		dfs1(tp[v] = v,u);
	ed[u] = tot;
}

int main(){
	
	freopen("1.in","r",stdin);
	
	read(n);
	rep(i,1,n-1){
		int u,v;read(u) , read(v);
		G[u].pb(v) , G[v].pb(u);
	}
	dfs0(1,0) , dfs1(tp[1] = 1,0);
	read(q);
	for(int op,u;q--;){
		read(op) , read(u);
		if(op == 1){
			int w = qry(ed[u]) - qry(st[u] - 1);
			if(w <= ans){
				DEL(P[tp[u]][0],C[0],0);
				W[u] = w , B[u] = 0;
				P[tp[u]][0].insert(u);
				INS(P[tp[u]][0],C[0],0);
			}
			else{
				DEL(P[tp[u]][1],C[1],1);
				W[u] = w , B[u] = 1 , ans++;
				P[tp[u]][1].insert(u);
				INS(P[tp[u]][1],C[1],1);
			}
			upd(st[u],1);
		}
		else{
			if(!B[u]){
				DEL(P[tp[u]][0],C[0],0);
				P[tp[u]][0].erase(u);
				if(!P[tp[u]][0].empty()){
					int a = *P[tp[u]][0].begin();
					W[a] = qry(ed[a]) - qry(st[a] - 1);
				}
				INS(P[tp[u]][0],C[0],0);
			}
			else{
				DEL(P[tp[u]][1],C[1],1);
				P[tp[u]][1].erase(u);
				if(!P[tp[u]][1].empty()){
					int a = *P[tp[u]][1].rbegin();
					W[a] = qry(ed[a]) - qry(st[a] - 1);
				}
				INS(P[tp[u]][1],C[1],1);
				ans --;
			}
			upd(st[u],-1);
		}
		
		for(;u;u=fa[tp[u]]){
			int p = tp[u];
			if(!P[p][0].empty() && st[*P[p][0].begin()] <= st[u]){
				int v = *P[p][0].begin();
				DEL(P[p][0],C[0],0);
				W[v]+=(op == 1 ? 1 : -1);
				INS(P[p][0],C[0],0);
			}
			if(!P[p][1].empty() && st[*P[p][1].rbegin()] <= st[u]){
				int v = *P[p][1].rbegin();
				DEL(P[p][1],C[1],1);
				W[v]+=(op == 1 ? 1 : -1);
				INS(P[p][1],C[1],1);
			}
		}
		
		if(op == 1){
			if(!C[0].G[ans+1].empty() && !C[1].G[ans].empty()){
				int u = C[0].G[ans+1].back() , v = C[1].G[ans].back();
				DEL(P[tp[u]][0],C[0],0);
				DEL(P[tp[u]][1],C[1],1);
				if(tp[v] ^ tp[u])
					DEL(P[tp[v]][1],C[1],1),
					DEL(P[tp[v]][0],C[0],0);
				P[tp[u]][0].erase(u);
				P[tp[u]][1].insert(u);
				P[tp[v]][1].erase(v);
				P[tp[v]][0].insert(v);
				int a = u;
				if(!P[tp[u]][0].empty()){
					a = *P[tp[u]][0].begin();
					W[a] = qry(ed[a]) - qry(st[a] - 1);
				}
				if(!P[tp[v]][1].empty()){
					a = *P[tp[v]][1].rbegin();
					W[a] = qry(ed[a]) - qry(st[a] - 1);
				}
				INS(P[tp[u]][0],C[0],0);
				INS(P[tp[u]][1],C[1],1);
				if(tp[u] ^ tp[v])
					INS(P[tp[v]][1],C[1],1),
					INS(P[tp[v]][0],C[0],0);
				swap(B[u],B[v]);
			}
			
			if(!C[0].G[ans+1].empty()){
				int u = C[0].G[ans+1].back();
				ans++;
				DEL(P[tp[u]][0],C[0],0);
				DEL(P[tp[u]][1],C[1],1);
				P[tp[u]][0].erase(u);
				P[tp[u]][1].insert(u);
				if(!P[tp[u]][0].empty()){
					int a = *P[tp[u]][0].begin();
					W[a] = qry(ed[a]) - qry(st[a] - 1);
				}
				INS(P[tp[u]][0],C[0],0);
				INS(P[tp[u]][1],C[1],1);
				B[u] = 1;
			}
			else if(C[0].G[ans].empty()){
				if(ans && !C[1].G[ans-1].empty()) {
					int u = C[1].G[ans-1].back();
					ans--;
					DEL(P[tp[u]][0],C[0],0);
					DEL(P[tp[u]][1],C[1],1);
					P[tp[u]][1].erase(u);
					P[tp[u]][0].insert(u);
					if(!P[tp[u]][1].empty()){
						int a = *P[tp[u]][1].rbegin();
						W[a] = qry(ed[a]) - qry(st[a] - 1);
					}
					INS(P[tp[u]][0],C[0],0);
					INS(P[tp[u]][1],C[1],1);
					B[u] = 0;
				}
			}
		}
		else{
			if(ans && !C[0].G[ans].empty() && !C[1].G[ans-1].empty()){
				int u = C[0].G[ans].back() , v = C[1].G[ans-1].back();
				DEL(P[tp[u]][0],C[0],0);
				DEL(P[tp[u]][1],C[1],1);
				if(tp[u] ^ tp[v])
					DEL(P[tp[v]][1],C[1],1),
					DEL(P[tp[v]][0],C[0],0);
				P[tp[u]][0].erase(u);
				P[tp[u]][1].insert(u);
				P[tp[v]][1].erase(v);
				P[tp[v]][0].insert(v);
				int a = u;
				if(!P[tp[u]][0].empty()){
					a = *P[tp[u]][0].begin();
					W[a] = qry(ed[a]) - qry(st[a] - 1);
				}
				if(!P[tp[v]][1].empty()){
					a = *P[tp[v]][1].rbegin();
					W[a] = qry(ed[a]) - qry(st[a] - 1);
				}
				INS(P[tp[u]][0],C[0],0);
				INS(P[tp[u]][1],C[1],1);
				if(tp[u] ^ tp[v])
					INS(P[tp[v]][1],C[1],1),
					INS(P[tp[v]][0],C[0],0);
				swap(B[u],B[v]);
			}
			if(!C[0].G[ans+1].empty()){
				int u = C[0].G[ans+1].back();
				ans++;
				DEL(P[tp[u]][0],C[0],0);
				DEL(P[tp[u]][1],C[1],1);
				P[tp[u]][0].erase(u);
				P[tp[u]][1].insert(u);
				if(!P[tp[u]][0].empty()){
					int a = *P[tp[u]][0].begin();
					W[a] = qry(ed[a]) - qry(st[a] - 1);
				}
				INS(P[tp[u]][0],C[0],0);
				INS(P[tp[u]][1],C[1],1);
				B[u] = 1;
			}
			else if(C[0].G[ans].empty()){
				if(ans && !C[1].G[ans-1].empty()) {
					int u = C[1].G[ans-1].back();
					ans--;
					DEL(P[tp[u]][0],C[0],0);
					DEL(P[tp[u]][1],C[1],1);
					P[tp[u]][1].erase(u);
					P[tp[u]][0].insert(u);
					if(!P[tp[u]][1].empty()){
						int a = *P[tp[u]][1].rbegin();
						W[a] = qry(ed[a]) - qry(st[a] - 1);
					}
					INS(P[tp[u]][0],C[0],0);
					INS(P[tp[u]][1],C[1],1);
					B[u] = 0;
				}
			}
		}
		printf("%d
",ans);
	}
}