레야몬

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 하면서 더하기 노드 ..

1. 문제 이 모듈은 사건 내에서 가능한 글자가 하나뿐이면 그 글자를 자동으로 입력한다. 모듈이 단어의 첫 글자를 추론하지 않는다. 사전의 모든 단어가 같은 알파벳으로 시작하더라도 반드시 첫 글자는 사용자가 버튼을 눌러 입력하여야 한다. 사건이 주어졌을 때, 이 모듈을 사용하면서 각 단어를 입력하기 위해 버튼을 눌러야 하는 횟수의 평균을 구하시오. 여러 개의 테스트 케이스로 주어져 있다. - 1 - 단어의 개수 \(N(1 \leq N \leq 10^{5})\) - N개의 줄 - 1~80글자인 영어 소문자로만 이루어진 단어. 똑같은 단어가 2번 이상 주어지지 않는다. 각 테스트 케이스마다 주어진 단어의 길이의 총합은 최대 \(10^{6}\)이다. 각 테케마다 문제의 정답을 소수점 둘째 자리까지 반올림하여 ..

1. 문제 그래프에서 정점의 부분 집합 S에 속한 모든 정점쌍이 인접하지 않으면 S를 독립 집합이라고 한다. 트리와 각 정점의 가중치가 양의 정수로 주어졌을 때, 최대 독립 집합을 구하시오. - 1 - 트리의 정점수 \(n(1 \leq n \leq 10,000)\) - 2 - n개의 정수, 정점 i의 가중치 \(w_{i}(1 \leq w{i} \leq 10,000, 1 \leq i \leq n)\) - 3 ~ 마지막 줄 - 정점의 쌍으로 간선이 주어짐 - 1 - 최대 독립집합의 크기 - 2 - 최대 독립집합에 속하는 정점을 오름차순으로 출력 최대 독립집합이 여러 개인 경우 하나만 출력하면 된다. 2. 재정의 트리에서 최대 독립 집합 구하기 3. 해결 방법 dp[no][0] += max(dp[next][0..

1. 문제 N개의 마을로 이루어진 나라가 있다. 마을에는 1~N까지의 번호가 붙어있다. 이 나라는 트리 구조이며 무방향성이다. N개의 마을 중 몇 개의 마을을 '우수 마을'로 설정하려고 한다. '우수 마을'로 선정된 마을 주민 수의 총합을 최대로 한다. '우수 마을'끼리는 서로 인접할 수가 없다. ;우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과 인접하여야 한다. - 1 - \(N(1 \leq N \leq 10,000)\) - 2 - 마을 주민 수 \(popu(0 \leq popu \leq 10,000)\) - M-1개줄 - 인접한 두 마을의 번호 '우수 마을'의 주민 수 총합 2. 재정의 트리에서 최대, 인접 X, 반드시 우수가 아닌 마을은 우수와 인접. 이때 최댓값은? 3. 해결 방..

1. 문제 성대 나라에는 각 도시별로 물탱크가 존재한다. 이 물탱크들은 모두 연결되어있으며 루트(수도)가 있는 트리의 형태를 가진다. A번 도시에 물을 채우면 수도에서부터 A번 도시까지 있는 경로에 수도부터 차례대로 1L, 2L, ..., (수도에서 A번까지의 도시 수)L 만큼 추가된다. 균관이는 어느 도시에 몇 리터의 물이 저장되어 있는지 알기 원한다. 균관이를 도와주는 프로그램을 작성하자. - 1 - 도시의 수 \((1 \leq N \leq 200,000)\), 수도 번호 \(C(1 \leq C \leq N)\) - N-1개 - 연결되어있는 두 도시의 번호쌍 x, y \((1 \leq x, y \leq N, x \neq y)\) - N+1 - 질의의 수 \(Q(1 \leq Q \leq 200,000)..

1. 문제 모든 판매원은 사수가 배정되며 한 회원당 단 한 명씩만 배정된다. 어떤 회원 A가 손해를 보면 그 회원의 모든 부사수도 같은 손해를 보고, 반대로 이익이 생기면 모든 부사수가 같은 이익을 본다. 승범이는 다음 두 종류의 명령을 처리하려 한다. 1 i w : 작은 i가 w만큼 이익/손해를 본다. 2 i : 직원 i의 현재 통장 잔액 출력 직원들은 빈 통장을 갖고 시작하며, 이익과 손해가 실시간으로 통장에 기록된다. 물론 통장 잔액은 음수일 수도 있다. -1- 판매원의 수 \(N(1 \leq N \leq 100,000)\), 명령의 수 \(M(1 \leq M \leq 100,000)\) 판매원들은 1~N번호로 매겨지며 승범이는 항상 1이다. -2- 1~N 사수가 순서대로 주어진다. 승범이는 사수가..

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번째 값..