sparse talbe 썸네일형 리스트형 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.. 더보기 이전 1 다음