BOJ 13309 - 트리 (레이지, ett, 트리)

https://www.acmicpc.net/problem/13309

트리+세그 공부하게 된 계기

 

<문제설명>

최대 2e5개의 정점을 갖는 루트가 1인 트리가 주어진다. 다음 쿼리를 처리하라

 

x y 1 : 정점x,y를 잇는 경로가 있다면 "YES"출력 후 x와 x의부모를 잇는 간선 제거

         없다면 "NO" 출력 후 y와 y의 부모를 잇는 간선 제거

x y 0 : 정점x,y를 잇는 경로가 있다면 "YES", 없다면 "NO" 출력

 

<풀이1>

정점 u와 p[u]의 간선을 끊는 것을 한 쪽의 색을 칠한다고 생각해보면 다음과 같다.

     

u와 A의 크기가 더 작을 경우 u쪽을 새로 칠하고 p[u]와 B의 크기가 더 작을 경우 p[u]쪽의 색을 새로 칠한다면 amortized log시간에 쿼리를 처리할 수 있다. (점점 색칠할 영역이 반절로 줄어듦)

 

두 부분 중 어느쪽이 작은지 판단하는 것을 u와 p[u]부터시작하는 multi source bfs로 구현하면 로그시간에 색을 칠해줄 수 있다

 

만약 u와 v사이에 경로가 있다면 두 색이 같을 것.

 

 

 

<코드>

int n, q, clr[MAX], p[MAX], vst[MAX];
vector<int> g[MAX];

void color(int u, const int nt, const int c, const int t) {
	clr[u] = c;
	for (int v : g[u]) if (v != nt && clr[v] == t) 
		color(v, nt, c, t);	
}

bool chk(int x, int y, const int c) { //x쪽이 더 작으면 true반환
	queue<P> q;
	q.push({ x,0 });
	q.push({ y,1 });
	vst[x] = vst[y] = c;
	while (!q.empty()) {
		int qSize = q.size();
		while(qSize--){
			int u, id;
			tie(u, id) = q.front(); q.pop();

			bool flag = false;
			for (int v : g[u]) if(vst[v]!=c && clr[v]==clr[u]){
				if ((id == 0 && v != y) || (id == 1 && v != x)) {
					vst[v] = c;
					q.push({ v,id });
					flag = true;
				}
			}
			if (!flag) return !id;
		}
	}
	return true;
}

int main() {
	FAST; cin >> n >> q;
	for (int i = 2,x; i <= n; i++) {
		cin >> x;
		p[i] = x;
		g[i].push_back(x);
		g[x].push_back(i);
	}
	for (int i = 0,u,v,opt; i < q; i++) {
		cin >> u >> v >> opt;
		cout << (clr[u] == clr[v] ? "YES" : "NO") << '\n';
		if (!opt) continue;
		if (clr[u] == clr[v]) chk(u, p[u], i) ? color(u, p[u], i+1, clr[u]) : color(p[u], u, i+1, clr[p[u]]);
		else chk(v, p[v], i) ? color(v, p[v], i+1, clr[v]): color(p[v], v, i+1, clr[p[v]]);
	}
}

 

 

 

<풀이2>

정점마다 ett번호를 부여한다면, 어떤 정점을 기준으로 후손노드들의 번호는 조상노드들의 번호보다 항상 크다.

 

정점마다 가장 높이 도달할 수 있는 조상정점의 ett번호를 유지한다면, 그 값이 바로 집합의 대표값이 된다.

 

<코드>

const int MAX = 2e5 + 4;
const int SMAX = (1<<19);

int n, qq, seg[SMAX], lazy[SMAX], l[MAX], r[MAX]; //seg엔 ett구간 최대
vector<int> g[MAX];

int c;
void dfs(int u) {
	l[u] = ++c;
	for (int v : g[u])dfs(v);
	r[u] = c;
}

void propagate(int i, int ns, int ne) {
	if (lazy[i] == 0) return;

	if (i < SMAX / 2) {
		lazy[i * 2] = max(lazy[i * 2], lazy[i]);
		lazy[i * 2+1] = max(lazy[i * 2+1], lazy[i]);
	}

	seg[i] = max({ seg[i], lazy[i] });
	lazy[i] = 0;
}

void update(int s, int e, int k, int i, int ns, int ne) {
	propagate(i, ns, ne);

	if (e < ns || ne < s) return;
	if (s <= ns && ne <= e) {
		lazy[i] = k;
		propagate(i, ns, ne);
		return;
	}
	int md = (ns + ne) / 2;
	update(s, e, k, i * 2, ns, md);
	update(s, e, k, i * 2+1, md+1, ne);
	seg[i] = max( seg[i * 2], seg[i * 2 + 1] );
}
void update(int s, int e, int k) {
	return update(s, e, k, 1, 0, SMAX / 2 - 1);
}

int val(int s, int e, int i, int ns, int ne) {
	propagate(i, ns, ne);
	if (e < ns || ne < s) return 0;
	if (s <= ns && ne <= e) return seg[i];
	int md = (ns + ne) / 2;
	return max(val(s, e, i * 2, ns, md), val(s, e, i * 2 + 1, md + 1, ne));
}
int val(int s) {
	return val(s, s, 1, 0, SMAX / 2 - 1);
}

int main() {
	FAST; cin >> n >> qq;
	for (int i = 2,x; i <= n; i++) {
		cin >> x;
		g[x].push_back(i);
	}
	dfs(1);
	fill(seg, seg + SMAX, 1);

	for (int i = 0, x, y, d; i < qq; i++) {
		cin >> x >> y >> d;
		if (val(l[x]) == val(l[y])) {
			cout << "YES\n";
			if(d==1) update(l[x], r[x], l[x]);
		}
		else {
			cout << "NO\n";
			if (d == 1) update(l[y], r[y], l[y]);
		}
	}
}