레야몬

1. 문제 N개의 중점으로 된 트리가 있다. 1~N번 매겨져 있고 간선은 1~N-1번 매겨져 있다. 아래 두 쿼리를 수행하는 프로그램을 작성하시오. 1 u v : u->v 경로 비용 출력 2 u v k : u->v 경로 정점 중 k번째 정점 출력 k는 u->v 경로에 포함된 정점 수보다 작다. - 1 - \(N(2 \leq N \leq 100,000)\) - N-1 개줄 - i번 간선 u->v와 비용 \(w(1 \leq w \leq 1,000,000)\) - N+1 - 쿼리의 개수 \(M(1 \leq M \leq 100,000)\) - M개의 줄 - 쿼리 각 쿼리 결과 출력 2. 재정의 X 3. 해결 방법 트리 노드 차수 degree 설정 희소 배열 비용, 노드 메모 비용 : LCA 하면서 더하기 노드 ..

LCA 2 하위 호환이라서 똑같은 코드로 바로 풀었다. 정답은 아래 링크에 있다. https://leyamon.tistory.com/entry/C-11438%EB%B2%88-LCA-2-%EC%9E%90%EB%A3%8C-%EA%B5%AC%EC%A1%B0-%ED%8A%B8%EB%A6%AC-%EC%B5%9C%EC%86%8C-%EA%B3%B5%ED%86%B5-%EC%A1%B0%EC%83%81-%ED%9D%AC%EC%86%8C-%EB%B0%B0%EC%97%B4 [C++] 11438번 LCA 2 - 자료 구조, 트리, 최소 공통 조상, 희소 배열 문제 N(\(2 \leq N \leq 100,000\))개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1부터 N가지 번호가 매겨져 있으며 루트는 1이다. 각 ..

문제 N(\(2 \leq N \leq 100,000\))개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1부터 N가지 번호가 매겨져 있으며 루트는 1이다. 각 노드의 쌍 M(\(1 \leq M \leq 100,000\))개가 주어졌을 때 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력하라. 노드의 개수 N 트리 상에 연결된 두 정점 (2~N) 가장 가까운 공통 조상을 알고 싶은 쌍의 개수 M 정점 쌍 (N+1+M) M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다. 문제 재정의 스패닝 트리가 주어질 때 최소 공통 조상을 출력하라. 해결 방법 희소 배열로 부모 저장, LCA로 빠르게 탐색 실수한 점, 개선한 점 MAX_LOG의 크기를 가진 배열에 MAX_LOG번째 값..

#include #include #include #include #define FOR(i, k, N) for(int i=k; i0; i++) { if(dif%2) { //Bit 계산 Min = min(Min, min_R[a][i]); Max = max(Max, max_R[a][i]); a = PA[a][i]; } dif = dif>>1; } } if(a != b) { for(int k=MAX_TR-1; k>=0; k--) { if(PA[a][k] && PA[b][k] && PA[a][k]!=PA[b][k]) { Min = min({Min, min_R[a][k], min_R[b][k]}); Max = max({Max, max_R[a][k], max_R[b][k]}); a = PA[a][k]; b=PA[b]..

#include #include #include #include #define FOR(i, k, N) for(int i=k; i> N; FOR(i, 1, N-1) { int a, b, r; cin >> a >> b >> r; Vertex[a].push_back({b, r}); Vertex[b].push_back({a, r}); } } void CD(int no, int Depth) //깊이 설정하기(lca 용) { vi[no]=1; FOR(i, 1, Vertex[no].size()) { if(!vi[ Vertex[no][i-1].Vr ]) { PA[Vertex[no][i-1].Vr][0]=no; PA[Vertex[no][i-1].Vr][1]=Vertex[no][i-1].R; CD(Vertex[no][i-..