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 todo[u] : u가 끝점인 쿼리들의 인덱스. w = lca(u,v)라고 할 때, 다음 그림의 색칠한 부분에 쿼리에서 물어본 타입이 있는지 처리해주면 된다. dfs를..
2020. 4. 1.
BOJ 3176 - 도로 네트워크 (LCA)
https://www.acmicpc.net/problem/3176 유독 LCA 코드를 짤 때 오타를 많이 내는것 같다. 최대크기 1e5인 간선 가중치가 있는 트리가 주어질 때, 1e5개의 쿼리에 답하는 문제. 쿼리 u, v : 정점u,v 사이의 경로 중 간선의 최소값과 최대값을 출력. u,v사이의 경로는 유일하다. 쿼리에 log(n)만에 답해야 한다. lca(u,v) 에서 u,v를 올려줄 때 그 과정을 따라가면서 간선 가중치 최소, 최대값(mn,mx)를 갱신할 것이기 때문에 depth를 이용하는 코드를 사용할 것이다. lca알고리즘을 다시 떠올려보자. u,v중 깊이가 더 깊은 정점을 u라고 강제하고, 1. u의 깊이를 v의 깊이에 맞춰 올려준다. 2. 같아진 u,v 깊이를 lca 직전까지 끌어올려준다. ..
2020. 1. 9.
