흔들리는 독립집합
다이아몬드 I의견: 0
\(N\)개의 정점으로 이루어진 트리가 있다. 정점 \(v\)에는 가중치 \(w_v\)가 있다.
트리의 독립 집합이란 어떤 두 정점도 간선으로 직접 연결되어 있지 않은 정점들의 집합을 말한다. 독립 집합의 가중치는 그 집합에 속한 정점들의 가중치 합이다.
이제 \(Q\)개의 갱신을 순서대로 처리한다. 각 갱신은 한 정점의 가중치를 새 값으로 바꾼다. 매 갱신 직후, 트리 전체에서 가중치 합이 최대인 독립 집합의 가중치를 출력해야 한다.
가중치는 음수일 수도 있으며, 공집합도 독립 집합이므로 답은 항상 \(0\) 이상이다.
\(1 \le N \le 50{,}000\)
\(1 \le Q \le 50{,}000\)
\(-10^9 \le w_v, x \le 10^9\)
\(1 \le v \le N\)
첫 줄에 정점 수 \(N\)과 갱신 수 \(Q\)가 주어진다.
둘째 줄에 \(N-1\)개의 정수가 주어지며 \(i\)번째 수는 정점 \(i+1\)의 부모 번호이다 (부모 번호는 항상 자식보다 작다).
셋째 줄에 \(N\)개의 정수 \(w_1, \dots, w_N\)이 주어진다.
이어서 \(Q\)개의 줄에 각각 두 정수 \(v\), \(x\)가 주어지며, 정점 \(v\)의 가중치를 \(x\)로 바꾼다는 의미이다.
각 갱신 직후 최대 가중치 독립 집합의 가중치를 한 줄에 하나씩, 총 \(Q\)줄 출력한다.
4 2
1 2 3
3 5 4 2
2 10
4 1
12
11경로 1-2-3-4. 처음 w=[3,5,4,2]. 첫 갱신: 정점2의 가중치를 10으로 -> w=[3,10,4,2]. 최적 독립집합은 {2,4}=12. 둘째 갱신: 정점4를 1로 -> w=[3,10,4,1]. 최적은 {2,4}=11 또는 {1,3}=7 중 11. 출력 12, 11.
3 2
1 1
-1 5 3
1 2
2 -4
8
3별 모양: 1이 중심, 2,3이 잎. 처음 w=[-1,5,3]. 갱신1: 정점1을 2로 -> w=[2,5,3]. 잎 둘 다 고르면 {2,3}=8(서로 연결 안됨). 갱신2: 정점2를 -4로 -> w=[2,-4,3]. 최적은 {1,3}? 1과 3은 연결되어 불가. {3}=3 vs {1}=2 -> 3. 출력 8, 3.
riseoj 작성
출처 Original
평가 및 의견
흔들리는 독립집합
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
흔들리는 독립집합