ABC350 G - Mediator

Competitive Programming C++ AtCoder Algorithms

2024-04-21

공식 에디토리얼

문제 링크
https://atcoder.jp/contests/abc350/tasks/abc350_g

원문 링크
https://atcoder.jp/contests/abc350/editorial/9821

그래프 전체가 트리의 집합 형태이기 때문에, 질문 쿼리에 대해 다음이 성립합니다.

• 만약 \(u\)와 \(v\)가 다른 연결 요소에 속하는 경우, 조건을 만족하는 정점은 존재하지 않는다.
• \(u\)와 \(v\)가 같은 연결 요소에 속하는 경우, 다음이 성립한다.
  • 그 연결 요소 중 적당한 정점을 루트로 하는 트리를 생각해본다.
  • 이 때, 조건을 만족하는 정점 \(w\)가 존재한다면, [\(w\)는 \(u\)의 부모 노드] 또는 [\(w\)는 \(v\)의 부모 노드] 중 하나인 것이 성립한다.

만약 으프라인으로 풀 수 있다면, 쿼리를 먼저 모두 읽어들인 다음에 연결 요소들에 대해서 적당한 루트를 잡고소 각 노드에 대해 부모 노드를 구한 다음에, 해의 후보가 될 수 있는 최대 \(2\)개의 노드가 적당히 존재하는가(간선 \(u - w\) 간선 \(v - w\)가 질문 쿼리 시점에 존재하는가) 를 판별하는 것으로 문제를 풀 수 있습니다.

하지만, 쿼리가 암호화 되어있기 때문에, 쿼리를 먼저 읽어들여 푸는 것은 어렵습니다. 따라서, 온라인으로 문제를 푸는 방법을 생각해봅시다.

여기서, 다음과 같이 쿼리 제곱근 분할 이라는 기법을 활용합니다.

• 쿼리를 크기 \(B\)씩의 블록으로 분할한다.
• 각 블록을 처리하기 시작하기 전에, 지금까지 쿼리 전체에 대해 \(O(N)\)의 시간복잡도가 소요된다.
• 각 블록의 범주에서, 그 블록 안에서 발생하는 변경 쿼리 마다의 시간복잡도는 \(O(B)\) 정도에 반영된다.
• 그 결과, 전체 시간복잡도는 \(O(\frac{NQ}{B} + BQ)\)가 된다. \(B = \sqrt{N}\)으로 잡게 되면 이를 \(O(Q\sqrt{N})\)에 수행할 수 있다.

각 블록의 처리를 시작할 때의 처리
그 때까지 추가된 간선에 대해 트리들을 구성합니다.
그로부터 모든 연결 요소들에 대해 위에서 설명한 것처럼 루트를 잡고 부모를 구해 둡니다.

여기서, 이 시점의 그래프 \(G_i\) 에 대해, 어느 정점이 어느 연결 요소에 있는지를 구해둡니다.

각 블록 안에서의 쿼리의 처리
간선의 추가는 단순히 [이 간선을 추가했다]고 기억해 둡시다.

질문 쿼리는 블록 시작 시점의 그래프 \(G_i\)를 보고, 다음의 케이스 워크를 합니다.

• \(G_i\)에서 \(u\)와 \(v\)가 같은 연결 요소에 속하는 경우
  • 위와 마찬가지로, 조건을 만족하는 정점은 \(u\)의 부모 노드나 \(v\)의 부모 노드 중 하나입니다.
• \(G_i\)에서 \(u\)와 \(v\)가 다른 연결 요소에 속하는 경우
  • 만약 조건을 만족하는 정점 \(w\)가 존재한다면, 그 블록 안에 \(u - w\)로의 간선 또는 \(v - w\)로의 간선이 추가되어 있어야 합니다. 블록 안의 간선들은 많아야 \(B\)개입니다.

이상의 내용을 구현하는 것으로 문제를 \(O(Q\sqrt{N})\)의 시간복잡도로 풀 수 있습니다.(하지만, 일반적인 구현으로는 \(\log\)가 붙으므로, 이것이 마음에 들지 않는다면 \(B\)를 조정해서 더 빠르게 할 필요가 있을지도 모릅니다.)