반응형 트리와 쿼리21 백준 13511번 : 트리와 쿼리 2 (C/C++) 백준 13511번 주어진 쿼리에 대해 답하는 문제이다. 백준 1761번: 정점들의 거리 백준 11438 : LCA 2 아래 배열을 정의한다. depth[x] : 루트로부터 정점 x까지의 거리 lev[x] : 루트를 기준으로 정점x의 레벨 pa[x][i] : 정점 x의 2^i번째 부모 우선 dfs탐색을 통해 depth, lev, pa배열을 채운다. l = lca(u, v)라고 할때, 쿼리1은 (depth[u]-depth[l])+(depth[v]-depth[l])로 구할 수 있다. 쿼리 2는 u부터 시작하여 k번 탐색을 진행하여야하는데 매 쿼리마다 k번의 탐색을 하면 시간초과가 날 것이다. 효율적인 풀이를 위해 경우를 나눈다. 1. k < lev[u]-lev[l]+1 인 경우 : u의 k-1번째 부모를 구한.. 2023. 5. 6. 이전 1 다음 반응형
