[BOJ 21853] 도로 폐쇄

문제

https://www.acmicpc.net/problem/21853

 

풀이 (Subtask 4)

$k$를 고정하고, Tree-DP를 사용합니다.

• 정점 $v$에서, 서브트리가 조건을 만족하고, $v$는 자식 정점과 연결되는 간선을 $k-1$개 이하가 되도록 할 때 가중치 합의 최솟값을 $A_v$라고 합시다.
• $v$에 대한 추가 조건이 없는 경우의 가중치 합의 최솟값을 $B_v$라고 합시다.

정점 $v$를 고정하고, $v$의 자식 정점의 집합을 $S$라고 합시다. 또한 $w(a, b)$를 $a$와 $b$를 잇는 간선의 가중치라고 합시다.

• $v$와 연결할 자식 정점의 집합을 $T$라고 합시다. 해당 자식 정점은, 부모와 이미 간선 $1$개가 이어져있기 때문에, $k-1$개의 간선만 이을 수 있습니다.
• 나머지 정점에 대해서는 $k$개의 간선을 모두 이을 수 있습니다.
• $A_v$ 와 $B_v$는 모두 $\min_{T \subset S} \sum_{t \in T} A_t + \sum_{s \in S} (B_s + w(s, v))$로 계산됩니다.
  • 단, $A_v$는 $|T| \le k-1$, $B_v$는 $|T| \le k$라는 추가 조건이 존재합니다.
  • 이는 $A_t - (B_t + w(t, v))$ 순으로 정점 $t$를 $k-1$개 혹은 $k$개 이하 고르면 해결할 수 있습니다.

해당 풀이를 구현 하면 $O(N^2)$ 혹은 $O(N^2 \log N)$에 문제를 해결할 수 있습니다.

풀이

이제 Full Subtask를 풀기 위한 관찰을 해 봅시다.

• 고정된 $k$에 대해서, 차수가 $k$ 이하가 되도록 고려해야 할 정점은 차수가 $k$ 초과인 정점입니다.
  • 나머지 정점은 간선을 하나도 지우지 않아도 차수가 $k$ 이하가 됩니다.
• $0$ 이상 $N-1$ 이하의 각 $k$에 대해서, 차수가 $k$ 초과인 정점의 개수를 세어보면, 이 정점 개수의 총합은 $2N-2입니다.
  • 차수가 $d$인 정점은 $k = 0, 1, \cdots, d-1$일 때만 세어지기 때문에, 총 $d$번 세어집니다.
  • 정점은 차수의 총합만큼 세어지고, 그래프의 차수의 총합은 $2N-2$이다.

이제 트리 DP를 그대로 사용하는데, 차수가 $k$ 이하여서 무시되는 정점들을 효율적으로 계산할 방법이 필요합니다. 차수가 $k$ 이하인 정점은, $A$와 $B$값 모두 $0$입니다. (어떠한 정점도 지울 필요가 없습니다.) 이 조건은 리프에 대해서도 만족하기 때문에, 차수가 $k$ 이하인 정점을 리프로 취급해도 됩니다. 그러므로, 다음과 같은 알고리즘이 동작합니다.

 

1. $k = 1, \cdots, N-1$에 대해 다음을 반복합니다.

1. 차수가 $k$ 초과인 정점들을 모아서, 포레스트를 만듭니다.
2. 나머지 정점을 모두 리프로 취급하고, 위의 동적 계획법을 씁니다.

• 차수가 $k$ 초과인 정점의 개수는 $O(N)$개 이지만, 리프 노드의 개수는 제한이 되어있지 않습니다.
• 매 순간 마다 차수가 $k$ 이하여서 무시되는 정점을 효율적으로 처리할 수 있는 자료구조가 존재하는 경우에는, 다음과 같은 알고리즘을 생각할 수 있습니다.

2. $k = 1, \cdots, N-1$에 대해 다음을 반복합니다.

1. 차수가 $k$인 정점 $v$에 대해서 다음을 반복합니다.
   1. $v$의 이웃 중 차수가 $k$ 초과인 정점 $u$에 대해서, $w(v, u)$의 가중치를 가진 자식이 존재한다는 체크를 합니다.
2. 차수가 $k$ 초과인 정점들을 모아서, 포레스트를 만듭니다.
3. 위의 동적 계획법을 계산합니다.
   1. 각 정점 $v$의 자식 $t$에 대해, $A_t$와 $B_t + w(t, v)$의 가중치를 가진 자식이 존재한다는 체크를 합니다.
   2. $A_t - (B_t + w(t, v))$에 따라 상위 $k, k-1$개의 합을 구합니다.
   3. 각 정점 $v$의 자식 $t$에 대해, $A_t$와 $B_t + w(t, v)$의 가중치를 가진 자식을 삭제합니다.

이 알고리즘의 amortized된 부분은 다음과 같습니다.

• 1-1-1의 과정은 총 $N-1$번 이하로 수행됩니다.
• 2의 과정에서, 정점의 개수는 총$N-2$개 입니다.
• 3-1, 3-3은 총 $N-2$번 이하로, 3-2는 $N-2$번 수행됩니다.

이제, 우리가 원하는 자료구조는 다음과 같은 형태입니다.

• $(A, B)$의 쌍을 추가하거나 제거합니다.
• $A$를 최대 $k$개, 나머지를 $B$를 골라 합을 최소화 합니다.

모두 $B$를 고른다고 가정 한 후에, $A-B$의 합 상위 $k$개를 더하면 됩니다. 여러가지 구현이 가능하며, 2번 쿼리의 $k$가 항상 증가하는 순으로 질문이 들어온다는 사실을 이용해도 됩니다. 해당 사실을 이용하면, std::map등의 자료구조를 사용해서, 상위 $k$번째 원소의 iterator를 유지하면서, $A-B$의 상위 $k$개 합과 전체 $B$의 합을 관리해 주면 됩니다.

코드: https://www.acmicpc.net/source/share/1e7a440ca10c4040b9c7a8b802d61435