본문 바로가기

lca

BOJ)13511 트리와 쿼리2 문제: icpc.me/13511 트리에서 2가지 종류의 쿼리를 수행하는 문제이다. 1번 쿼리의 경우 정점들의 거리와 같은 문제로 트리의 루트로 부터 정점 x로의 거리를 dist[x]라고 하였을 때 1번 쿼리의 답은 dist[u]+dist[v]-2*dist[lca(u,v)]가 된다. 왜 이렇게 되는지는 그림을 그려보면 쉽게 알 수 있다. 2번 쿼리는 lca를 구할 때 만든 sparse table을 이용해줄 수 있다.(선형으로 탐색할 경우 시간초과를 피할 수 없다.) 만약 dph[x]-dph[lca]가 z-1보다 크거나 작다면 x를 z-1번 올려주면 되고 (올려줄 때 sparse table을 이용하여 log시간에 올려주어야 한다.) 아닌 경우 두 경로사이에 속한 정점의 수 -z 만큼 y를 올려준다. 1234.. 더보기
BOJ)10637 Minimum Spanning Tree 문제: icpc.me/10637 간선들의 셋이 주어진다. 출력해야하는 답은 각 간선마다 자신을 제외한 간선들로 만들 수 있는 MST의 가중치의 합을 출력하는 문제이다. 이건 MST에 포함 안되는 간선에 대한 답은 MST의 가중치가 되겠지만 아닌 경우가 문제가 된다. 그렇다면 아닌 경우에 대해 생각해보자. 만약에 MST에 포함되지 않는 간선이 u-v 를 연결한다고 생각해보자 그러면 우리는 mst에서 u v를 잇는 경로상의 어떤 간선을 지워도 이 간선을 통하여 MST를 유지 할 수 있다. 즉 이러한 사실을 이용하여 MST를 만들 때 사용되지 않은 간선들을 가중치 순서대로 정렬하여 오프라인으로 미리 mst상에 사용 된 간선들의 답을 정해주는 것이다. 여기서 매번 경로를 확인해준다면 당연히 TLE를 보게 될 것.. 더보기
트리에서 A와 B의 경로 사이에 C존재 여부 트리에서 임의의 노드 A,B가 있을 때 A와 B의 경로에 C가 존재하는지 여부는 어떻게 알 수 있을까? A와 B의 LCA를 LCA(A,B)라고 칭해보자. 만약 A와 B의 경로사이에 C가 존재한다면 C는 A와 LCA(A,B) 사이의 경로에 존재하거나 B와 LCA(A,B) 사이의 경로에 존재할 것이다. 일단 A와 LCA(A,B) 사이의 경로에 C가 존재한다고 가정해보자 그렇다면 LCA(A,C)==C && LCA(A,B)==LCA(C,B) 가 성립할 것 이다. 그러면 이번에는 B와 LCA(A,B)사이의 경로에 C가 존재한다고 가정해보자. 그렇다면 LCA(B,C)==C && LCA(A,B)==LCA(C,A) 가 성립할 것이다. 따라서 { LCA(A,C)==C && LCA(A,B)==LCA(C,B) }|| { L.. 더보기
BOJ)13309 트리 문제:icpc.me/13309 트리에서 두 가지 쿼리를 처리하는 문제이다. 첫번 째 쿼리는 두 정점이 같은 컴포넌트에 존재하는지 여부이고 두번 째 쿼리는 두 정점이 같은 컴포넌트에 존재하는지 여부를 물음과 동시에 존재할 경우 두 정점 x,y 중 x와 x의 부모의 간선을 단절 존재하지 않을 경우 y와 y의 부모의 간선을 단절 시키는 쿼리이다. 오래 생각하다가 못 풀겠어서 풀이를 봤는데 재밌는 문제였다. 우선 루트에서 DFS를 돌면서 정점들의 번호를 방문하는 순서대로 새롭게 매겨준다. 이렇게 하면 어떤 정점 A의 자식들은 모두 A보다 큰 번호를 연속적으로 가지게 된다. 이걸 이용하여 정점 A부터 A의 자식들까지 범위를 저장해놓고 있을 수 있다. 그렇다면 두 정점이 같은 컴포넌트인지 확인하는 경우를 올라갈 수.. 더보기
BOJ)1396 크루스칼의 공 문제: icpc.me/1396 lca를 이용하는 난이도 있는 문제다. 풀이 방법이 재밌다. x정점에서 y정점으로 이동할 때의 최소온도는 도로네트워크 등의 문제에서 했듯이 두 정점 사이의 lca를 구해나가면서 해당 간선의 가중치의 최댓값도 parent 배열과 같이 저장하는 방법으로 구해낼 수 있으나 공이 움직일 수 있는 범위를 출력하는게 문제가 되었다. 오래 생각해도 모르겠어서 찾아보니까 재밌는 방법으로 이걸 해결할 수 있었다. MST를 구성하는 과정에서 두 정점을 연결하는 대신 새로운 정점을 생성하는 방법이다. 즉 기존의 정점들은 새로운 그래프에서의 leaf가 되며 n-1개의 정점을 새로 구축하는 방법이다. 예제의 그래프를 새로 구축하면 이런 모양이 될 것이다. (기존의 정점(1~5)) 여기서 새로 생기.. 더보기
BOJ)1626 두 번째로 작은 스패닝 트리 문제: icpc.me/1626 두 번째로 작은 스패닝 트리를 구하는 문제이다. 우선 정점이 V개 간선이 E개인 그래프에서 MST를 구해준다. 그리고 MST를 구성할 때 사용하지 않은 E-V+1개의 간선에 대해서 해당 간선을 포함하는 MST를 구하여 답을 구해낸다.. 하지만 E-V+1번 크루스칼을 돌린다면 TLE를 보게 될것이다. 그렇다면 E-V+1개의 간선을 각각 포함하는 MST를 어떻게 구해낼 수 있을까? 우선 현재 보고 있는 간선이 1번 정점과 5번 정점을 연결한다고 가정해보자. 그렇다면 우리는 기존의 MST에서 1번 정점과 5번 정점을 연결해주어 N개의 간선을 가진 그래프를 생각해보자. 해당 그래프를 트리로 만드려면 하나의 간선을 제거해야한다. 이 때 제거되야 되는 간선은 1번 정점과 5번 정점을 .. 더보기
BOJ)10838 트리 문제: icpc.me/10838 트리에서 세가지 쿼리를 처리하는 문제이다. 1번 쿼리나 3번 쿼리에서 물어보는 질의를 답하기 위해서는 a와 b의 lca를 필수적으로 구해야한다. 고정된 트리에서 LCA는 전처리를 거친후에 logN의 시간에 구할 수 있지만 2번 쿼리가 트리의 구조를 바꿔버리기 때문에 힘들어질 뿐더러 1번, 3번 쿼리를 처리하기 위해 LCA를 구했다고 하더라도 색칠을하거나 색의 개수를 세려면 log시간에 처리하긴 힘들어보인다. 하지만 문제를 잘 읽어보면 paint와 count 연산 시 a번 노드와 b번 노드 사이의 최단경로의 길이는 항상 1,000 이하이다. 라는 조건을 찾을 수 있다. 이를 이용하여 LCA나 쿼리를 O(1000)의 시간에 해결해주면 문제를 해결할 수 있다. 123456789.. 더보기
Persistent Segment Tree 먼저 시작하기 전에 .. -오늘 공부한 내용을 제 멍청한 머리가 기억하지 못할까봐 기록하는 개인용 글입니다. -해당 자료구조에 대하여 완벽하게 알고 적는 글이 아니기 때문에 Persistent segment tree를 공부하는 용도로는 좋지 못한 글이 될 확률이 높습니다.-BOJ 11932 문제를 풀기 위해 https://hongjun7.tistory.com/m/64와 http://blog.myungwoo.kr/100 를 많은 부분에서 참고하였습니다. persistent segment tree가 뭔지는 알고있었지만 귀찮아서 공부를 미루다가 오늘 BOJ 11932번을 접하고 도전하게 되었다. persistent segment tree는 가상의 N개의 세그먼트 트리를 O(NlogN)의 공간복잡도로 유지하는 .. 더보기
BOJ)2233 사과나무 문제:icpc.me/2233 트리가 주어질 때 루트에서 DFS를 탐색하는 순서대로 0은 노드를 처음 방문할 때 1은 노드에서 더 이상 탐색이 불가능하여 return 될 때를 순서대로 수열로 나타낼 때 썩은 사과 2개를 동시에 제거 가능한 가장 가까운 노드의 0과 1의 위치를 출력하는 문제이다. 우리는 썩은 사과 2개가 주어질 때 동시에 제거 가능한 가장 가까운 노드를 LCA를 통하여 구할 수 있다. 0과 1로 이루어진 수열에서 0일 경우에는 노드를 추가하고 현재 보는 노드의 자식으로 설정 1일 경우에는 현재 보고 있는 노드의 부모를 현재 보고있는 노드로 설정해 주어 깊이와 부모를 구해준 후 LCA를 구해주면 된다. 12345678910111213141516171819202122232425262728293.. 더보기
BOJ)8012 한동이는 영업사원! 문제:icpc.me/8012 한동이가 방문해야 할 도시를 x->y->z->w 순이라면 x->y의 거리와 y->z의 거리 z->w의 최소시간을 더해서 출력하는게 답이된다. 결국 N,M제한 때문에 거리를 logN의 시간복잡도에 해결을 해줘야하는데 우리는 주어진 그래프가 트리라는걸 이용하여 LCA를 통하여 계산해 줄수 있다. x와 y의 최단 거리는 결국 모든 간선의 가중치가 1이니까 깊이를 이용하여 dph[x]+dph[y]-2*dph[lca(x,y)] 로 계산할 수 있다. 이를 이용하여 답을 구해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#in.. 더보기

티스토리툴바