BOJ 13512 트리와 쿼리 3

ㅎㅇ!
오늘은 트리와 쿼리 3을 들고 왔다!

문제: 트리와 쿼리 3

HLD를 안다면, 크게 어려워할 문제는 아닐거라 생각한다.
HLD에서 dfs ordering과 chain의 생성을 담당하는 부분(위 글에서 dfs2 함수)을 잘 살펴보면, 1에서부터 모든 정점 v까지의 경로에 포함되는 정점들의 order는 깊이가 깊어짐에 따라 순 증가함을 알 수 있다.
이를 이용해 정점이 흰색일때는 그 점에 해당하는 세그먼트 트리의 노드에 적당히 큰 수를 넣고, 그렇지 않을 때는 그 정점의 order을 넣어주는 식으로 최솟값 세그먼트 트리를 작성하면 되겠다.

#include<bits/stdc++.h>
using namespace std;

#define radj(x) for(int nxt:adj[x])
#define fastio do{ios::sync_with_stdio(0);cin.tie(0);}while(0)

const int nmax = 100010;
const int inf = 1e9;

int n,m;
vector<int> adj[nmax];
int w[nmax],d[nmax],p[nmax];
int hld[nmax],idx[nmax],rev[nmax];
int seg[nmax<<2];
int col[nmax<<2];

/*Minimum Segment Tree - begin*/
void su(int idx,int l,int r,int p,int v){
	if(l>p||r<p)return;
	if(l!=r){
		int mid=l+r>>1;
		su(idx<<1,l,mid,p,v);su((idx<<1)+1,mid+1,r,p,v);
		seg[idx]=min(seg[idx<<1],seg[(idx<<1)+1]);
        return;
	}
	seg[idx]=v;
}
int sq(int idx,int l,int r,int s,int e){
	if(l>e||r<s)return inf;
	if(s<=l&&r<=e)return seg[idx];
	int mid=l+r>>1;
	return min(sq(idx<<1,l,mid,s,e),sq((idx<<1)+1,mid+1,r,s,e));
}
/*Minimum Segment Tree - end*/

/*HLD - begin*/
void dfs(int now,int dep){
	d[now]=dep;
	w[now]=1;
	radj(now)if(!w[nxt]){
		p[nxt]=now;
		dfs(nxt,dep+1);
		w[now]+=w[nxt];
	}
}
int dn=0;
void dfs2(int now){
	int cc=-1;
	idx[now]=++dn;
	rev[idx[now]]=now;
	radj(now)if(p[nxt]==now&&(cc==-1||w[nxt]>w[cc])){
		cc=nxt;
	}
	if(cc!=-1){
		hld[cc]=hld[now];
		dfs2(cc);
	}
	radj(now)if(p[nxt]==now&&nxt!=cc){
		hld[nxt]=nxt;
		dfs2(nxt);
	}
}
void upd(int u){
	col[u]^=1;
	su(1,1,n,idx[u],col[u]?idx[u]:inf);
}
int query(int u){
	int r=inf;
	while(hld[u]!=hld[1]){
		r=min(r,sq(1,1,n,idx[hld[u]],idx[u]));
		u=p[hld[u]];
	}
	r=min(r,sq(1,1,n,idx[hld[u]],idx[u]));
	return r;
}
/*HLD - end*/

int main(void){
	fastio;
	hld[1]=1;
	cin>>n;
	for(int i=1;i<n;i++){
		int a,b;
		cin>>a>>b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(1,1);dfs2(1);
	for(int i=1;i<=n;i++)su(1,1,n,idx[i],inf);
	cin>>m;
	while(m--){
		int a,b;
		cin>>a>>b;
		if(a==1){
			upd(b);
		}
		else{
			int r=query(b);
			cout<<(r==inf?-1:rev[r])<<"\n";
		}
	}
}