BOJ 18263 - Milk visits(오프라인 쿼리, lca)

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

솔루션 참고. 오프라인 쿼리 중 처음 보는 접근.

온라인 쿼리로 풀 수는 있다고 하지만 떠오르지 않는다

 

<문제설명>

트리가 주어지고, 각 정점마다 type이 주어진다.

(정점, type 모두 최대 1e5)

 

최대 1e5개의 쿼리가 들어온다.

u, v, t : u~v 경로상에 type t가 존재하는가?

 

 

<풀이>

트리의 루트부터 차례로 순회하면서, 현재 정점이 u일때, u가 끝점인 쿼리들을 처리해 줄 것.

 

dat[i][0], dat[i][1] : i번째 쿼리의 첫번째 끝점, 두번째 끝점

vector<int> todo[u] : u가 끝점인 쿼리들의 인덱스.

w = lca(u,v)라고 할 때, 다음 그림의 색칠한 부분에 쿼리에서 물어본 타입이 있는지 처리해주면 된다.

dfs를 돌며 현재 정점이 u일 때, (1~u) 경로 중 type t를 갖는 정점들을 구분한 벡터 sav[t]를 유지해준다. (2차원 배열 안에 최대 n개 정점 들어가니 메모리 괜찮음)

 

처리중인 쿼리에서 물어본 type t를 갖는 정점이 sav[t]에 있다면 sva[t]에 가장 마지막에 추가된 요소가 u와 가장 가까운 점이므로 그 정점 x = sav[t].back()에 대해서만 생각해주면 된다.

 

x가 v의 조상이 아니라면 x는 색칠한 영역에 있는 것이므로 해당 쿼리는 참이 된다.

 

w의 type이 t라면 해당 쿼리는 참이다.

 

v~w 영역은 나중에 dfs로 v를 방문할 때 처리해준다.

 

 

<코드>

const int MAX = 1e5 + 4;

int n, m, breed[MAX], p[MAX][20], tin[MAX], tout[MAX], counter;
int dat[MAX][2], c[MAX]; // query;
bool ans[MAX];
vector<int> g[MAX], todo[MAX];

void dfs(int u, int prv) {
	tin[u] = counter++;
	for (int v : g[u]) if (v != prv) {
		p[v][0] = u;
		for (int i = 1; (1 << i) < n; i++)
			p[v][i] = p[p[v][i - 1]][i - 1];

		dfs(v, u);
	}
	tout[u] = counter++;
}

bool isAncestor(int u, int v) { // u가 v의 조상인지
	return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int lca(int u, int v) {
	if (isAncestor(u, v)) return u;
	if (isAncestor(v, u)) return v;

	for (int i = 19; i >= 0; i--)
		if (p[u][i] != 0 && !isAncestor(p[u][i], v))
			u = p[u][i];
	return p[u][0];
}

vector<int> sav[MAX];
void dfs2(int u, int prv) {
	sav[breed[u]].push_back(u);
	for (int i : todo[u]) if (!sav[c[i]].empty()) {		//u를 끝점으로 물어본 쿼리 처리
		int v = dat[i][0] + dat[i][1] - u;				//u가 아닌 다른 끝점
		if (breed[u] == c[i]) ans[i] = true;			
		else if (breed[lca(u, v)] == c[i]) ans[i] = true;
		else {
			int x = sav[c[i]].back();					//색칠한 영역에 들어갈 후보 정점
			if (!isAnscestor(x, v)) ans[i] = true;		//w보다 depth가 낮은 경우
		}
	}
	for (int v : g[u]) if (v != prv) dfs2(v, u);
	sav[breed[u]].pop_back();
}

int main() {
	FAST; cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> breed[i];
	for (int i = 0, u, v; i < n - 1; i++) {
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1, 0);

	for (int i = 0; i < m; i++) {
		cin >> dat[i][0] >> dat[i][1] >> c[i];
		todo[dat[i][0]].push_back(i);
		todo[dat[i][1]].push_back(i);
	}
	dfs2(1, 0);
	for (int i = 0; i < m; i++) cout << ans[i];
	cout << '\n';
}

 

<생각>

isAncestor(int u, int v) 만으로도 해결할 수 있는 것이 많은 것 같다.