마을 경비대 배치
골드 IV의견: 0
마을에는 \(N\)명의 경비원 후보가 있고, 이들은 트리 모양의 친목 관계로 연결되어 있다. 각 경비원 후보 \(i\)는 보안 능력치 \(a_i\)를 가지고 있다.
마을 대장은 다음 규칙에 따라 경비원을 배치하려 한다:
- 서로 친목 관계(트리에서 인접한 두 노드)에 있는 두 경비원 후보를 동시에 배치할 수 없다.
배치된 경비원들의 보안 능력치 합을 최대화하는 배치를 구하여라. 아무도 배치하지 않을 수도 있다.
- \(1 \le N \le 200\,000\)
- \(1 \le a_i \le 10^9\)
- 주어진 그래프는 트리임이 보장된다.
첫째 줄에 경비원 후보의 수 \(N\)이 주어진다.
둘째 줄에 \(N\)개의 정수 \(a_1, a_2, \dots, a_N\)이 공백으로 구분되어 주어진다.
다음 \(N-1\)개의 줄에 친목 관계 \((u, v)\)가 한 줄에 하나씩 주어진다. 관계는 양방향이다.
배치된 경비원들의 보안 능력치 합의 최댓값을 출력한다.
1
7
7
경비원이 하나뿐이므로 그 경비원을 배치하면 보안 값 \(7\)을 얻는다.
5
3 1 4 1 5
1 2
2 3
3 4
4 5
12
경로 트리 \(1-2-3-4-5\)에서 인접한 두 경비원을 동시에 배치할 수 없다. 홀수 번 경비원 \(\{1, 3, 5\}\)를 배치하면 보안 값 합이 \(3+4+5=12\)로 최대이다.
4
10 3 3 3
1 2
1 3
1 4
10
중심 경비원 \(1\)만 배치하면 보안 값 \(10\)이다. 잎 경비원 \(\{2,3,4\}\)를 모두 배치하면 \(3+3+3=9\)이므로, 최대는 \(10\)이다.
riseoj 작성
출처 Original
평가 및 의견
마을 경비대 배치
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
마을 경비대 배치