DSU tree

DSU 트리는 DSU 로 만들어진 집합에서 세그먼트트리를 돌리기 위해 만들어진 트리입니다.

 

1. merge 부분

 

merge 를 할 때 일반적으로는 두 정점의 boss 정점이 다르면 그냥 두 정점의 boss 를 이어주는 식으로 해결했지만 

DSU tree 에서는 새 정점을 만든 뒤 두 정점의 boss 를 새 정점으로 이어주고 간선도 만들어줍니다.

 

수도 코드로 표현하면 이렇습니다.

 

void merge(int x,int y){
	x = find(x);
	y = find(y);
	if(x!=y){
		n++;
		uf[n] = n;
		uf[x] = n;
		uf[y] = n;
		v[n].push_back(x);
		v[n].push_back(y);
	}
}

 

그렇게 되면 boss 정점을 기준으로 tree 가 만들어지게됩니다.

 

2. find 부분

 

find 부분은 기존과 같이 돌리면 됩니다.

 

int find(int x){
	if(uf[x]!=x) return uf[x] = find(uf[x]);
	return x;
}

 

3. dfs ordering

 

dfs 오더링을 해서 boss 정점으로 기준으로 만든 트리에서 세그먼트 트리를 만들어줍니다.

 

void dfs(int x){
	len[x].x = tmp;
	for(int e=0;e<sz(v[x]);e++){
		int nx = v[x][e];
		dfs(nx);
	}
	len[x].y = tmp++;
}
void mk_len(){
	for(int e=1;e<=n;e++){
		if(find(e)==e){
			dfs(e);
		}
	}
}

 

이렇게 한 뒤 세그먼트 트리를 만들어서 쿼리를 처리해주면 됩니다.

 

 

관련 문제

 

codeforces.com/contest/1416/problem/D