반응형 ps연습장14 백준 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. 백준 25638번 : 트리와 경로 개수 쿼리 (C++) 백준 25638번 q개의 쿼리에 대해 정점 u를 지나는 경로의 개수를 구하는 문제이다. 정점 u에 대해서 다음과 같이 2개의 트리로 쪼개 진다고 가정해보자. 트리 x에대해 빨간점의 개수를 red[x], 파란점의 개수를 blue[x]라고 정의할때, 경로의 개수는 red[1]*blue[2] + blue[1]*red[2]개이다. 따라서 각각의 트리에 대해 red[x], blue[x]를 구하는 것이 핵심이라고 할 수 있다. 그러나 모든 쿼리마다 각각의 트리의 red[x], blue[x]를 계산하면 시간 초과가 날 것이 뻔하다. 보다 효율적인 방법을 생각해보자. 우선 풀이의 편의성을 위해 루트를 1로 설정하겠다. 그리고 임이의 정점u를 아래 그림으로 나타내었다. r[x], b[x]를 아래와 같이 정의해주자 r[x.. 2023. 5. 5. 이전 1 2 3 4 다음 반응형
