21728번 - 트리와 2개의 지름 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 (추가 시간 없음) | 1536 MB | 5 | 4 | 3 | 100.000% |
문제
이메이미 교수의 알고리즘 과목을 재수강하게 된 메시는 작년과 같은 실수를 반복하지 않기 위해 중간고사를 철저히 대비하려고 한다. 작년에 가중치 없는 트리의 지름에 관련된 문제가 나왔던 것을 참고하여, 메시는 다음과 같은 문제를 스스로 고안해내었다.
"가중치 없는 트리 $T$에 대해, 두 정점을 잇는 최단경로 중 가장 긴 것들을 $T$의 지름이라고 한다. $T$의 지름들의 모임을 $\mathcal{D}_{T}$라고 하자. $T$의 두 지름 $D, E \in \mathcal{D}_{T}$에 대해 (둘은 같을 수 있다), 둘 모두에 공통으로 속하는 정점의 개수를 $f(D, E)$라 하자. 가능한 모든 $D, E$에 대한 $f(D, E)$의 합 $F(T) = \sum_{D \in \mathcal{D}} \sum_{E \in \mathcal{D}} f(D, E)$를 구하여라."
$N$개의 정점을 가진 트리에는 최대 $O(N^2)$개의 지름이 있기 때문에, 메시는 모든 지름을 구해서 각각이 공통으로 소유하는 정점 개수를 구하는 방식으로 훌륭한 $O(N^5)$ 코드를 구현해냈다. 이 정도라면 아무리 어려운 이메이미 교수의 시험이라도 통과할 수 있을 것만 같았다.
하지만 작년 시험에서 메시를 좌절시켰던 것은 무수한 양의 쿼리였기 때문에, 심기일전한 메시는 쿼리에 대한 대비도 미리 하고자 한다. 간선을 연결하거나 제거하는 쿼리를 추가하기 위해, 맨 처음에 주어지는 그래프를 트리가 아니라 포레스트로 바꿨다. 즉, 그래프에 여러 개의 연결 컴포넌트가 있을 수도 있다.
쿼리는 다음 중 하나로, 총 $Q$개 주어진다.
$1$ $x$ $y$ : 정점 $x$와 $y$를 연결한다. 이 쿼리가 들어올 때 정점 $x$와 $y$는 서로 다른 연결 컴포넌트에 있다.
$2$ $x$ $y$ : 정점 $x$와 $y$를 연결하는 간선을 제거한다. 이 쿼리가 들어오기 전에 정점 $x$와 $y$를 연결하는 간선이 존재한다.
$3$ $x$ : 정점 $x$가 포함되는 트리 $T$에 대해 $F(T)$를 $10^9+7$로 나눈 나머지를 출력한다. 이 쿼리가 들어오기 전에 정점 $x$가 포함된 연결 컴포넌트에는 정점이 2개 이상 존재한다.
메시는 훌륭한 $O(QN^{5})$ 코드를 완성한 뒤 당신에게 검수를 부탁했다. 이 문제를 풀고 큰 데이터를 추가해서 메시가 중간고사를 잘 볼 수 있도록 도와주자.
입력
입력의 첫 줄에 정점의 개수 $N$, 간선의 개수 $M$, 쿼리의 개수 $Q$가 주어진다.
다음 $M$줄에는 초기 상태의 간선이 연결하는 두 정점의 번호 $x, y$가 주어진다. 정점의 번호는 $1$번부터 $N$번까지이다.
다음 $Q$줄에는 각 쿼리를 나타내는 정보가 주어진다.
출력
$3$번 쿼리가 들어올 때마다 $F(T)$를 $10^9+7$로 나눈 나머지를 출력한다.
제한
- $2 \le N \le 100\,000$
- $0 \le M \le N - 1$
- 입력으로 주어지는 그래프는 포레스트이다.
- $1 \le Q \le 100\,000$
- $3$번 쿼리가 하나 이상 존재한다.
예제 입력 1
7 5 5 1 2 1 3 2 4 2 5 3 6 3 1 1 3 7 3 1 2 2 1 3 1
예제 출력 1
18 64 21
출처
Contest > BOJ User Contest > IDTcup > 제 3회 IDTcup D번
Camp > Petrozavodsk Programming Camp > Winter 2022 > Day 2: Grand Prix of Daejeon J번
Contest > Open Cup > 2021/2022 Season > Stage 11: Grand Prix of Daejeon J번
- 문제를 만든 사람: imeimi2000
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호