2024 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2024 Winter) Open

- 차종 $B$에 대한 가상 검증 수행은 도훈이만 할 수 있기 때문에 $T_B \times V_B$의 시간이 확정적으로 소요됩니다.
- 차종 $A$에 대한 가상 검증 항목을 도훈이가 $X$개, 상혁이가 $V_A-X$개 맡는다면 가상 검증 업무를 완료하는 데 소요되는 시간은 $\max(X \times T_A + T_B \times V_B, (V_A-X) \times T_A )$ 입니다.

- $V_A$의 값이 크지 않기 때문에 $0 \leq X \leq V_A$의 모든 $X$에 대해 소요되는 시간을 구하고, 그 중 최솟값을 출력하면 됩니다. 총 시간 복잡도는 $\mathcal{O}(Q \times V_A)$ 입니다.

2024 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2024 Winter) Open - A - Editorial

$\binom{N}{3}$개 삼각형을 모두 확인하는 당연한 풀이는 시간복잡도가 $\mathcal{O}\left(N^3\right)$입니다.
또한 소위 불도저 트릭이라고 불리기도 하는 rotating sweep line method를 생각하셨다면, 일반적인 풀이에 대해 공간 복잡도가 $\mathcal{O}\left(N^2\right)$가 됩니다.
이 두 가지보다는 좀 더 효율적인 알고리즘을 소개합니다.

## 알고리즘

- 어떤 한 점 $P$를 기준으로 나머지 $N-1$개 점을 (반)시계방향으로 정렬합니다.

- 점 $P$와 정렬에서 이웃한 두 점으로 만들어지는 $N-1$개 삼각형의 높이 중 가장 짧은 것을 찾습니다.

- 이 과정을 모든 점에 대해 $N$번 반복하여 그 중 가장 짧은 높이를 찾아줍니다.

이 알고리즘을 구현하면 시간복잡도 $\mathcal{O}\left(N^2 \log N\right)$, 공간복잡도 $\mathcal{O}\left(N\right)$에 문제를 해결할 수 있습니다.

## 증명

어떤 세 점이 한 직선 위에 있으면, 알고리즘이 $0$이라는 답을 찾을 것입니다. 그렇지 않은 경우, 위 알고리즘이 가장 짧은 높이를 찾지 못한다고 가정합시다. 

- 삼각형 $\triangle P P_1 P_2$가 알고리즘이 찾지 못한 가장 짧은 높이를 가지는 삼각형이라고 합시다. 일반성을 잃지 않고, $P_1$에서 $\overline{PP_2}$에 내린 수선의 높이가 가장 짧다고 합시다. 이때, $\angle P_1 P P_2$를 항상 예각으로 만들 수 있음을 관찰할 수 있습니다.

- 알고리즘이 이 삼각형을 찾지 못했으므로, $P_1$과 $P_2$는 $P$를 기준으로 정렬했을 때 서로 이웃한 점이 아니게 됩니다.
다시 말해, 어떤 $P'$이라는 점이 존재해 반직선 $\overrightarrow{PP'}$이 선분 $\overline{P_1 P_2}$를 지나게 됩니다.

- $\angle P_1 P P' < \angle P_1 P P_2 < 90^{\circ}$이기 때문에, $P_1$을 $\overline{PP'}$에 내린 수선의 길이, 즉 $P_1$에 대한 삼각형 $\triangle{PP_1P'}$의 높이가 $\triangle{PP_1P_2}$의 높이보다 짧습니다.

2024 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2024 Winter) Open - B - Editorial

각 바이러스는 $T$초 후 상하 방향과 좌우 방향 모두 최대 $T$칸 이동 가능합니다. 단, 바이러스가 스펀지 밖으로 나갈 수 없으니 $T$초 후에도 스펀지의 범위 내에 있어야 합니다. 즉, 각 바이러스의 이동 범위를 $(X,Y)$로 표현하면 $\max(1,x_{i}-T) \leq X \leq \min(x_{i}+T, W)$, $\max(1,y_{i}-T) \leq Y \leq \min(x_{i}+T,H)$ 이 됩니다.

각 바이러스가 이동할 수 있는 경우의 수는 $(X,Y)$ 범위 직사각형의 면적이며, 이는 $(\min(x_{i}+T,W) - \max(1,x_{i}-T)+1) \times (\min(y_{i}+T,H) - \max(1,y_{i}-T)+1)$ 입니다. 각 바이러스는 모두 독립적으로 이동 가능하므로, 이들의 경우의 수를 모두 곱한 것을 $998\,244\,353$으로 나눈 나머지가 답이 됩니다.

2024 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2024 Winter) Open - C - Editorial



$C_x$를 $A$에 존재하는 $x$의 개수라고 정의합시다. Jiro가 배열을 바꿀 때, $0$을 $x$로 바꾼 횟수를 $B_x$로 고정하면 이는 다음 조건을 만족해야 합니다.

- $A_x + B_x \le x$ $(1 \le x \le N)$
- $B_1 + B_2 + \cdots + B_N = C_0$

이 때 조건에 맞게 만들 수 있는 경우의 수는  $\dfrac {C_0!}{B_1! B_2! \cdots B_N!} $으로 계산할 수 있습니다.

### $\mathcal O(N^3)$ 풀이

이 문제를 효율적으로 구하기 위해 동적계획법을 사용합시다.

- $dp_{i,\ j}$: $1, \cdots, i$까지의 수를 이용해서 $j$개의 $0$을 다른 수로 바꿨을 때 나올 수 있는 경우의 수
  - 분모의 $C_0!$을 이용하기 위해서, $(C_0 - j)$개의 $0$을 서로 다른 임의의 기호로 채웠다고 가정합니다.

위에 정리한 내용을 이용하면

$$ \displaystyle{dp_{i,\ j} = \sum_{k=0}^{x-B_x} \dfrac{dp_{(i-1),\ (j-k)}}{k!}}$$ 으로 계산할 수 있습니다. 

### $\mathcal O(N^2 \log N)$

위 식을 NTT를 이용해서 최적화 할 수 있습니다. $dp_i$를  $\left\{dp_{(i-1),\ x}\right\}_{0 \le x \le C_0}$와 $\left\{\frac{1}{x!}\right\}_{0 \le x \le i - B_i}$ 의 합성곱으로 나타낼 수 있으며, 이를 이용해서 구한 $dp_{N,\ C_0}$가 최종적인 답이 됩니다.


### 추천 문제
[13184 카드](https://www.acmicpc.net/problem/13184)

2024 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2024 Winter) Open - D - Editorial

문자열 $S$로 만든 그래프가 주어진 그래프와 같다는 것은 다음 두 가지를 모두 만족함을 의미합니다.

- 두 그래프에서 등장하는 서로 다른 간선의 가짓수가 동일합니다.
- $S$로 만든 그래프가 주어진 그래프의 부분그래프입니다.

이 두 가지를 모두 만족하는 범위를 두 포인터 등을 이용하면서 구할 수 있습니다.

## 두 포인터

$T_i\cdots T_j$에서 $T_{j+1}$이 문자열에 추가된 경우, $T_j T_{j+1}$이 이루는 간선이 그래프에 추가됩니다. 또한, $T_i$가 문자열에서 제외된 경우 $T_i T_{i+1}$이 이루는 간선이 삭제됩니다.

간선의 중복도가 $0$에서 $1$, 혹은 $1$에서 $0$으로 바뀌는 시점을 기준으로:

- 서로 다른 간선의 가짓수를 갱신해 주면, $\mathcal O (1)$에 부분문자열의 간선의 가짓수 변화를 처리할 수 있습니다.

- 간선의 중복도가 $1$ 이상이면서, 주어진 그래프에서 등장하지 않는 간선의 개수를 세어 주면, $\mathcal O (1)$에 부분그래프인지 여부를 처리할 수 있습니다.


$r_1$이 $T_i \cdots T_{r_1}$로 만든 그래프가 주어진 그래프와 간선 개수가 같아지는 최소 위치이고, $r_2$가 $T_i \cdots T_{r_2}$로 만든 그래프가 주어진 그래프의 부분그래프가 아니게 되는 최소 위치라고 하면, 문자열 $S$의 $i$번째 문자로 시작하는 부분문자열 중 주어진 그래프와 같아지는 경우의 수는 $\max(r_2-r_1, 0)$입니다.

$i$가 증가함에 따라, $r_1$과 $r_2$ 모두 증가하므로 문자열에서 문자의 삽입 삭제는 총 $\mathcal O(N)$번 일어나게 되므로, 총 $\mathcal O(N)$ 시간 복잡도에 문제를 해결할 수 있습니다. 

2024 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2024 Winter) Open - E - Editorial

$N \le 5 \times 10^5$이므로 모든 경우를 백트래킹으로 시도해보는 $\mathcal{O}(N!)$의 풀이는 너무 느립니다. 따라서, 일일이 모든 경우의 수의 작업을 수행하지 않고 원하는 색깔의 배열을 만드는 방법을 찾아야 합니다.

## 관찰
$N-1$개의 인접한 두 호떡 쌍에 대해 서로 다른 색깔의 인접한 두 호떡 쌍의 위치에 대해 관찰합시다.

- 모든 호떡을 뒤집어도 $D$는 변하지 않고 일정합니다.

- 한 작업에서 $x$번째와 $x+1$번째의 호떡 색깔이 같은 $x$를 골랐다고 생각하면, $x$번째와 $x+1$번째의 호떡 색깔이 달라지고, 나머지에 대해서는 인접한 두 호떡 쌍의 색이 다른 여부가 달라지지 않습니다.

## 풀이
편의상, 새로운 배열 $T$를 다음과 같이 정의하겠습니다.

- $T$: $S_i \neq S_{i+1}$인 모든 $i$의 값을 오름차순 정렬한 배열

만약 현준이가 원하는 배열을 만들 수 있다면, 이전 관찰에 따라 작업 횟수 $K$는 $\lvert T \rvert (\le N-1)$라는 것을 알 수 있습니다. 또한, $T$의 원소 중 하나라도 작업에서 $x$로 사용하지 않는다면 원하는 배열을 만들 수 없습니다. 따라서, $T$를 적절히 재배열해서 작업 순서를 정해야 합니다.

$\lvert T\rvert \le 1$일 때는 모든 경우에 대해 조건 분기를 통해 답을 구할 수 있으므로, $\lvert T \rvert \ge 2$ 인 경우에 대해 다룹시다.

$T$를 아무렇게나 재배열하여 수행할 경우, 원하는 배열의 모든 색깔이 뒤집힐 수 있으므로 마지막 원소인 $S_N$과 작업을 모두 수행했을 때 마지막 호떡 색깔을 같은 색으로 맞춥시다.

- 먼저 순차적으로 $T_1, T_2, \cdots, T_{\lvert T\rvert - 2}$의 값을 $x$로 하는 작업을 수행해봅시다. 여러 번 작업을 해도 맨 마지막인 $N$번째 호떡의 색깔은 처음 `W`로 변하지 않습니다.

- 만약 $S_N$이 `W`라면 $T_{\lvert T\rvert -1}, T_{\lvert T \rvert }$ 순서로, $S_N$이 `B`라면 $T_{\lvert T \rvert }, T_{\lvert T \rvert -1}$ 순서로 작업을 수행해서, $S_N$의 색을 맞춰줍니다.

작업이 모두 끝난 후 $N$번째 호떡의 색깔과 $S_N$은 같으므로, 원하는 배열을 만들 수 있다는 사실을 알 수 있습니다. $\mathcal{O}(N)$의 시간복잡도로 이 문제를 해결할 수 있습니다.

2024 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2024 Winter) Open - F - Editorial

수열 $A$의 원소들에서 $k$번째 비트만을 참고해 새로운 수열 $B_k$를 만듭시다. 이 수열이 0과 1만으로 이루어져 있음은 자명합니다. 수열 $B_k$에서 구한 답이 $f(k)$라면, 전체 문제의 답은 $\sum_{k=0}^{29} 2^kf(k)$입니다. 이는 AND, OR, XOR의 세 경우에서 모두 성립합니다.

0과 1만으로 이루어진 수열 $B$에서의 답을 구할 수 있다면 문제를 $\mathcal{O}(N \log A)$ 시간복잡도에 해결할 수 있습니다. 자세한 방법은 다음과 같습니다.

## AND

두 인덱스 $1 \le x \le y \le N$에 대해, $(B_x \land B_{x+1} \land \cdots \land B_y)$가 1이려면 $B_x, B_{x+1}, \cdots, B_y$가 모두 1이어야 합니다. 따라서 1만으로 이루어진 연속된 부분수열들의 길이를 구한 뒤, 이를 $C_1, \cdots, C_m$이라 합시다. $\sum\limits_{i=1}^m {C_i+1 \choose 2}$가 문제의 답이 됩니다.

## OR

두 인덱스 $1 \le x \le y \le N$에 대해, $(B_x \lor B_{x+1} \lor \cdots \lor B_y)$가 0이려면 $B_x, B_{x+1}, \cdots, B_y$가 모두 0이어야 합니다. 따라서 0만으로 이루어진 연속된 부분수열들의 길이를 구한 뒤, 이를 $D_1, \cdots, D_l$이라 합시다. ${N+1 \choose 2} - \sum\limits_{i=1}^l {D_i+1 \choose 2}$가 문제의 답이 됩니다.

## XOR

수열의 누적 XOR 값을 저장한 배열 $S$를 $S_0 = 0, S_i = S_{i-1} \oplus B_i$로 정의합시다. XOR 연산은 자기 자신을 역원으로 가지기 때문에, 두 인덱스 $1 \le x \le y \le N$에 대해 $(B_x \oplus B_{x+1} \oplus \cdots \oplus B_y) = S_y \oplus S_{x-1}$이 성립합니다. 따라서 모든 $1 \le j \le N$에 대해, $0 \le i < j, S_i \oplus S_j = 1$을 만족하는 $i$의 개수 합을 구하면 됩니다.

두 배열 $Z_i, O_i$를 관리합시다. $Z_i = 0 \le j \le i, S_j = 0$인 $j$의 개수, $O_i = 0 \le j \le i, S_j = 1$인 $j$의 개수입니다.

$\sum_{i=1}^N \begin{cases}
 O_{i-1}, & if \ S_i = 0 \\
 Z_{i-1}, & if \ S_i = 1
 \end{cases}$ 이 문제의 답이 됩니다.

2024 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2024 Winter) Open - G - Editorial

$i, j$가 주어지는 시점의 $s_i, s_j$를 $s'_i, s'_j$라 합시다. $i, j$에 대응되는 수열 $a_1(=i), \dots, a_k$와 $b_1(=j), \dots, b_l$이 존재해서 $s'_i$는 $s_{a_1}, \dots, s_{a_k}$를, $s'_j$는 $s_{b_1}, \dots, s_{b_l}$를 순서대로 이어 붙인 문자열입니다.

$i, j$에 대응되는 수열의 마지막 원소를 관리하면서 $i, j$가 주어질 때마다 $a_k \rightarrow b_1$ 간선을 추가해 그래프를 구성합시다. 만들어지는 그래프는 $N - 1$개의 간선으로 이루어진 하나의 경로를 이루고, 경로를 따라가면서 $s_i$를 차례로 출력하면 문제를 해결할 수 있습니다.

풀이의 시간 복잡도는 $\mathcal{O}(N + \sum{|s_i|})$입니다.

### 코드 (C++)

```cpp
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;

int main() {
	fastio;
	int n, a, b; cin >> n;
	vector s(n + 1, string{});
	vector nxt(n + 1, 0), tail(n + 1, 0);
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
		tail[i] = i;
	}
	for (int i = 1; i < n; i++) {
		cin >> a >> b;
		nxt[tail[a]] = b;
		tail[a] = tail[b];
	}
	do cout << s[a]; while (a = nxt[a]);
}
```

### 코드 (Python)

```python
import sys
input = sys.stdin.readline

n = int(input())
s = [input().rstrip() for _ in range(n)]
nxt = [0 for _ in range(n + 1)]
tail = [_ for _ in range(n + 1)]

for _ in range(n - 1):
	a, b = map(int, input().split())
	nxt[tail[a]] = b
	tail[a] = tail[b]

for _ in range(n):
	print(s[a - 1], end='')
	a = nxt[a]
```

2024 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2024 Winter) Open - H - Editorial

### 관찰 1

칠판에 처음 적은 수가 $X$일 때, 게임을 진행하면서 칠판에 적을 수 있는 수는 $X$의 약수입니다. $X \leq 10^9$일 때 가능한 약수의 개수는 최대 $1\, 344$개 입니다. 따라서 게임이 진행되는 동안 칠판에 적힐 수 있는 최대 $1\, 344$개의 정수에 대해서만 고려해도 됩니다.

### 관찰 2

현재 칠판에 적힌 수가 $G$일 때, 지금까지 게임을 진행하면서 선택한 모든 카드들은 $G$의 배수입니다. 따라서 카드를 $2$가지의 경우로 나눌 수 있습니다.
1. $G$의 배수가 아닌 카드는 게임이 진행되는 동안 선택되지 않은 카드이고, 선택하면 칠판에 적힌 수가 바뀝니다. 
2. $G$의 배수인 카드는 게임이 진행된 턴의 수만큼 소모되었습니다. 이 카드는 선택해도 칠판에 적힌 수가 바뀌지 않기 때문에, 게임이 진행되는 동안 선택한 카드가 정확하게 어떤 카드인지 관리할 필요가 없습니다.

위의 사실로 현재 칠판에 적힌 수와 게임이 진행된 턴의 수만으로 모든 게임판의 상태를 표현할 수 있음을 관찰할 수 있습니다.

### 풀이

위에서 관찰한 사실로 다이나믹 프로그래밍 풀이를 유도할 수 있습니다. $C_G =$ 아무것도 선택하지 않은 카드 뭉치에서 $G$의 배수가 적힌 카드의 수, $dp[T][G] = T$번째 턴에 현재 칠판에 적힌 수가 $G$일 때 승패 여부라고 정의합니다. 아래의 경우 중 상대방이 패배하는 경우를 선택할 수 있다면 $dp[T][G]$일 때 승리합니다.

1. $G$의 배수가 아닌 카드를 선택하여 칠판에 새로 적히는 수가 $G'$일 때, $G' \neq 1$이면서 $dp[T+1][G']$가 패배하는 경우
2. $T \leq C_G$일 때, $G$의 배수인 카드를 선택하여 $dp[T+1][G]$가 패배하는 경우

정수 $X$의 약수의 개수를 $d(X)$라 할 때, 모든 $G$에 대한 $C_G$는 $\mathcal{O}(d(X) \times N)$에 전처리할 수 있습니다. $dp$의 상태는 $d(X) \times N$개이고 각 상태마다 최대 $N$개의 카드에 대해 최대공약수를 계산합니다.

총 시간복잡도는 HashMap을 잘 사용했을 때 $\mathcal{O}(d(X) \times N^2 \log{X})$ 입니다. 상수 커팅이 어느정도 적용되므로 해당 시간복잡도로 이 문제를 풀 수 있습니다. 현재 턴의 기우성에 대한 게임판의 상태를 관찰한다면 $\mathcal{O}(d(X) \times N \log{X})$의 시간복잡도로 문제를 해결할 수 있습니다.

2024 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2024 Winter) Open - I - Editorial

$f\left(i\right) = pi+q, g\left(j\right) = rj+s$로 정의합시다. $a \le i \le c$ 에 대해 $f\left(i\right)$는 전체 합에 $\left(d-b+1\right) \bmod B$번 더해집니다. 같은 이유로 $b \le j \le d$ 에 대해 $g\left(j\right)$는 $\left(c-a+1\right) \bmod B$번 더해집니다. 따라서 $\bigoplus\limits_{i=a}^c f\left(i\right) \otimes \left(\left(d-b+1\right) \bmod B\right), \bigoplus\limits_{j=b}^d g\left(j\right) \otimes \left(\left(c-a+1\right) \bmod B\right)$을 구하면 됩니다. 이때 $a \otimes b$는 $a$를 $b$번 $\oplus$연산한 수를 의미합니다.

답을 한 번에 구하기는 어렵습니다. 답의 각 자릿수에 해당하는 숫자를 따로 구해봅시다. 첫 자리에 해당하는 수는 자명하게 $\left(\left(d-b+1\right)\sum\limits_{i=a}^c f\left(i\right) + \left(c-a+1\right)\sum\limits_{j=b}^d g\left(j\right)\right) \bmod B$입니다. $B$진법의 구조상 두 번째 자리에 해당하는 수는 $\left(\left(d-b+1\right)\sum\limits_{i=a}^c \left\lfloor {f\left(i\right) \over B} \right\rfloor + \left(c-a+1\right)\sum\limits_{j=b}^d \left\lfloor {g\left(j\right) \over B} \right\rfloor\right) \bmod B$입니다. 결과적으로 $k$번째 자리에 해당하는 수는 $\left(\left(d-b+1\right)\sum\limits_{i=a}^c \left\lfloor {f\left(i\right) \over B^{k-1}} \right\rfloor + \left(c-a+1\right)\sum\limits_{j=b}^d \left\lfloor {g\left(j\right) \over B^{k-1}} \right\rfloor\right) \bmod B$임을 알 수 있습니다.

$\sum\limits_{x=0}^n \left\lfloor {ax+b \over c} \right\rfloor$ 꼴의 문제를 floor sum이라 하고, $\mathcal{O}\left(\log a\right)$ 시간복잡도에 해결할 수 있음이 알려져 있습니다. $\sum\limits_{i=a}^c \left\lfloor {f\left(i\right) \over B^{k-1}} \right\rfloor = \sum\limits_{i=0}^c \left\lfloor {f\left(i\right) \over B^{k-1}} \right\rfloor - \sum\limits_{i=0}^{a-1} \left\lfloor {f\left(i\right) \over B^{k-1}} \right\rfloor$임을 이용해 floor sum으로 원하는 값을 계산해줄 수 있습니다.

최종 시간복잡도는 $\mathcal{O}\left(K \log \max\left(pN, rM\right) \log \max\left(p, r\right)\right)$ 입니다.

2024 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2024 Winter) Open - J - Editorial

### 참고
- Easy ∙ Hard 문제가 출제 예정에 있습니다. Hint 1_Easy_ → Hint 2_이 문제_ → Hint 3_Hard_ 순의 접근으로 풀이의 흐름을 구분하겠습니다.
### 용어
해설에서 용어를,
- 트리, 정점, 간선으로 통일합니다.
- 정점의 색깔도 검은색 ∙ 흰색으로 통일합니다.
- 벙커가 있는 건물을 $M$이라고 부르겠습니다.

## Hint 1 $(N$: 홀수, $K \le 60)$

### 트리 크기가 $\mathbf{30}$ 이하
$M$만 검은색으로 칠해서 전달하면 됩니다.

### 동형 트리에서 변치 않는 것
트리를 마구 섞어도 센트로이드는 그대로 유지됩니다. 그렇다면, 색칠을 통해 센트로이드와 $M$간의 관계를 잘 설명하여 풀 수 있을 것 같습니다.
### 센트로이드부터 $M$까지
전체 트리의 센트로이드를 루트로 잡습니다. 루트부터 $M$까지 경로는 전부 검은색으로, 경로를 둘러싸는 정점들은 흰색으로 칠해봅시다. 그렇다면 $M$의 위치를 알아낼 수 있습니다!

하지만 최악의 경우 $\mathcal O(N)$의 횟수만큼 칠하게 됩니다. 따라서 다른 방법이 필요합니다. 센트로이드 분할 과정을 나타낸 센트로이드 트리로 바꿔 생각할 경우, 각 센트로이드를 경로처럼 생각하며 칠해줄 수 있다는 것을 알 수 있습니다. 다행히 차수가 $3$ 이하라는 조건이 있어, 이 경우 $\mathcal O(\log N)$만큼 색칠을 해두는 것으로 충분합니다.

### 센트로이드는 최대 두 개
하지만 센트로이드는 매번 유일하게 결정되지 않습니다. 단, 그렇게 많지도 않습니다. 최대 두 개 존재하고, 그럴 경우 연속하다는 성질을 갖습니다. 그럼 두 개의 센트로이드가 발생할 경우에 어떤 센트로이드를 선택해야 할 지 정해야 합니다.

이건 둘의 위치가 정확히 구분되기만 한다면 해결할 수 있는 문제인데, 이는 최초로 잡은 센트로이드를 루트로 한 트리에서 더 높은/혹은 더 낮은 센트로이드로만 선택하도록 약속해두어 구분할 수 있습니다!

## Hint 2 $(K \le 30)$

### 루트가 되는 센트로이드
그렇다면 전체 트리의 센트로이드를 유일하게 결정할 방법이 필요합니다. 여기에는 채색 정보를 활용할 수 있습니다. $N\le 30$를 예외처리해 두었다면, 남는 정점이 최소 하나는 존재합니다. 이 남는 정점으로 전체 색깔 $\text{XOR}$을 제어할 수 있습니다.

그렇다면 전체 트리의 두 연속한 센트로이드의 색을 다르게 하고, 전체 정점의 $\text{XOR}$과 같은 색의 센트로이드를 루트로 특정하면 됩니다. (이 방법이 유일하지는 않겠지만, 이게 제일 간단할 듯 싶습니다) 이러면 최대 $2$번의 추가적인 채색이 필요합니다.

이때 주의할 점은, 첫 번째 실행에서 선택하는 센트로이드가 $M$과 더 가까운 센트로이드가 되어야 한다는 것입니다. 그렇지 않으면 반대쪽 센트로이드가 $M$이 될 경우에 제대로 찾을 수 없기 때문입니다. (이렇게 ‘어떻게 특정할 것인가’를 두고 세세한 설정을 고려하는 과정이 꽤 어려운 것 같습니다)

### 엄밀한 계산
이제 이 방법에 필요한 채색 횟수의 상한을 엄밀하게 계산해봅시다.

최악의 경우 센트로이드 분할 과정에서 트리의 크기가 $1$이 되기 전까지 센트로이드가 $M$이 되지 않습니다. 그리고 센트로이드 분할 과정에서 최악의 경우 파고들어가는 서브트리의 크기는 현재 크기가 $S$라고 할 때, $\left \lfloor S/2\right \rfloor$가 됩니다. 센트로이드는 제외되기 때문이죠.

따라서 경로 속 정점과 경로를 둘러싸는 정점의 개수의 총합은 최대 $3\times\left \lfloor \log_2 N\right \rfloor$이 됩니다.
그리고 앞서 말했듯이 전체 트리의 센트로이드를 특정해야 하므로 $2$번이 더 소요됩니다.
이렇게만 할 경우, $\left\lfloor\log_2 1\,000\,000\right\rfloor = 19$이므로 $19\times 3 + 2 = 59$번의 색칠이 필요합니다.

하지만 경로 속 정점과 경로를 둘러싼 정점들을 전부 보면서 색깔을 바꿔야 하는 것의 개수를 센 뒤, 그것이 $58(=19\times 3+1)$의 절반인 $29$를 넘는다면 그 반대를 색칠해 주어서 동일한 결과를 얻을 수 있습니다.

따라서 총 $30$번의 색칠으로 $M$을 찾을 수 있습니다.
## Hint 3 $(K \le 20)$

### 도전!
한 가지의 색칠 최적화 전략을 더 떠올릴 수 있습니다. 화이팅!

2024 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2024 Winter) Open - K - Editorial

문제 조건에 의해 관리된 도로로 구성된 부분 그래프는 연결되어 있어야 합니다. 따라서 관리 비용을 최소화할 경우 관리된 도로가 구성하는 부분 그래프는 MST가 됩니다. $Q \le 2 \times 10^4$개의 쿼리에 대해 각각 MST의 가중치 합을 구해야 합니다. 그러나 총 $\mathcal{O}(QM\log N)$의 시간 복잡도로는 문제를 해결할 수 없습니다.

MST의 중요한 특성을 크루스칼 알고리즘에서 관찰할 수 있습니다. 크루스칼 알고리즘이 반환하는 결과는 가중치의 순서에 의존합니다. 다시 말해, 가중치의 값이 달라져도 순서가 같다면 MST는 달라지지 않습니다. 또한, 가중치가 같은 간선이 있다면 어떤 순서로 추가하더라도 MST의 가중치는 같습니다.

이제 가중치의 값이 최대 $5$가지이므로, 유의미한 가중치의 순서는 총 $5!=120$개입니다. 각각에 대해 크루스칼 알고리즘을 $\mathcal{O}(M \alpha(N))$ 또는 $\mathcal{O}(M \log N)$에 수행할 수 있습니다. 또는, 프림 알고리즘을 $\mathcal{O}(5M)$ 또는 $\mathcal{O}(M)$에 수행할 수 있습니다. 가중치의 가짓수를 $c$라고 하면, 총 $\texttt{(MST를 구하는 시간)}\times \mathcal{O}(c!)$에 전처리가 가능합니다.

전처리 과정에서 각 스패닝 트리에 대해, 각 학교에서 포함된 도로 수만 저장하도록 합니다. 이렇게 하면 한 스패닝 트리에 순서쌍을 대입한 후의 가중치 합을 $\mathcal{O}(c)$에 구할 수 있습니다. 주어진 관리비 순서쌍을 정렬하여 순서를 찾으면 각 쿼리를 $\mathcal{O}(c \log c)$에 해결할 수 있습니다.

이제 전체 문제를 $\mathcal{O}(c!M\alpha(N)+Qc\log c)$ 등의 시간 복잡도로 해결할 수 있습니다.

## 알고리즘별 디테일

크루스칼 알고리즘을 사용할 경우, 간선을 매번 정렬하여 해결하면 MST를 구하는 시간 복잡도는 $\mathcal{O}(M \log M)$이 됩니다. 가중치의 가짓수가 적기 때문에, 계수 정렬에서 아이디어를 빌려올 수 있습니다. 이때 분리 집합에서 한 가지 최적화를 사용하면 $\mathcal{O}(M \log N)$, 두 가지를 사용하면 $\mathcal{O}(M \alpha(N))$이 됩니다.

프림 알고리즘을 사용할 경우, 단순한 우선순위 큐를 사용하면 MST를 구하는 시간 복잡도는 $\mathcal{O}(M \log N)$이 됩니다. 가중치의 가짓수가 적기 때문에, Bucket Queue 자료구조에서 아이디어를 빌려와 시간 복잡도를 $\mathcal{O}(cM)$으로 만들 수 있습니다. $c=\mathcal{O}(1)$이라는 점에서, 비트마스킹을 사용하면 상수를 더 줄여 시간 복잡도를 $\mathcal{O}(M)$으로 만들 수 있습니다.

### 코드 (C++, 크루스칼, MST당 $\mathcal{O}(M \alpha(N))$)

```cpp
#include<bits/stdc++.h>
using namespace std;
using ll=long long;

struct UnionFind
{
 std::vector<int> par, cou;
 UnionFind(int N = 0) : par(N), cou(N, 1) { iota(par.begin(), par.end(), 0); }
 int find(int x) { return (par[x] == x) ? x : (par[x] = find(par[x])); }
 bool unite(int x, int y)
 {
 x = find(x), y = find(y);
 if (x == y) return false;
 if (cou[x] < cou[y]) std::swap(x, y);
 par[y] = x, cou[x] += cou[y];
 return true;
 }
 int count(int x) { return cou[find(x)]; }
 bool same(int x, int y) { return find(x) == find(y); }
 std::vector<std::vector<int>> groups()
 {
 std::vector<std::vector<int>> ret(par.size());
 for (int i = 0; i < int(par.size()); ++i) ret[find(i)].push_back(i);
 ret.erase(std::remove_if(ret.begin(), ret.end(),
 [&](const std::vector<int> &v) { return v.empty(); }),
 ret.end());
 return ret;
 }
};

int main()
{
 cin.tie(0)->sync_with_stdio(0);
 ll N,M,Q;cin>>N>>M>>Q;
 vector<pair<int,int>>edge[5];
 for(int i=0;i<M;i++)
 {
 int u,v;cin>>u>>v;
 char z;cin>>z;
 edge[z-'A'].emplace_back(u-1,v-1);
 }
 array<int,5>order{0,1,2,3,4};
 map<array<int,5>,array<ll,5>>CO;
 do
 {
 array<ll,5>coefs{};
 UnionFind UF(N);
 for(int w=0;w<5;w++)
 {
 for(auto[u,v]:edge[order[w]])
 {
 if(UF.unite(u,v))coefs[order[w]]++;
 }
 }
 CO[order]=coefs;
 }while(next_permutation(begin(order),end(order)));
 while(Q--)
 {
 array<ll,5>ws;
 for(ll&i:ws)cin>>i;
 array<int,5>srt{0,1,2,3,4};
 sort(begin(srt),end(srt),[&](int i,int j){return ws[i]<ws[j];});
 ll wgt=0;
 auto coef=CO[srt];
 for(int i=0;i<5;i++)
 {
 wgt+=ws[i]*coef[i];
 }
 cout<<wgt<<"\n";
 }
}
```

### 코드 (C++, 프림, MST당 $\mathcal{O}(M)$)

```cpp
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
 
int main()
{
 cin.tie(0)->sync_with_stdio(0);
 ll N,M,Q;cin>>N>>M>>Q;
 vector<vector<pair<int,int>>>adj(N);
 for(int i=0;i<M;i++)
 {
 int u,v;cin>>u>>v;
 char z;cin>>z;
 adj[u-1].emplace_back(z-'A',v-1);
 adj[v-1].emplace_back(z-'A',u-1);
 }
 array<int,5>order{0,1,2,3,4};
 map<array<int,5>,array<int,5>>CO;
 do
 {
 array<int,5>coefs{};
 vector<pair<int,int>>miniQ[5];
 int exist=0;
 vector<int>vis(N);
 int inv[5];
 for(int i=0;i<5;i++)inv[order[i]]=i;
 auto empty=[&]{return exist==0;};
 auto top=[&]->auto
 {
 // assume nonempty
 int mi=__builtin_ctz(exist);
 return pair{mi,miniQ[mi].back()};
 };
 auto pop=[&]->void
 {
 // assume nonempty
 int mi=__builtin_ctz(exist);
 miniQ[mi].pop_back();
 if(miniQ[mi].empty())exist^=1<<mi;
 };
 auto push=[&](int w,pair<int,int>edge)
 {
 miniQ[w].push_back(edge);
 exist|=1<<w;
 };
 push(0,{0,0});
 coefs[0]--;
 while(!empty())
 {
 auto[mi,pa]=top();
 pop();auto[col,v]=pa;
 if(vis[v])continue;
 coefs[col]++;vis[v]=1;
 for(auto e:adj[v])
 {
 if(!vis[e.second])push(inv[e.first],e);
 }
 }
 CO[order]=coefs;
 }while(next_permutation(begin(order),end(order)));
 while(Q--)
 {
 array<ll,5>ws;
 for(ll&i:ws)cin>>i;
 array<int,5>srt{0,1,2,3,4};
 sort(begin(srt),end(srt),[&](int i,int j){return ws[i]<ws[j];});
 ll wgt=0;
 auto coef=CO[srt];
 for(int i=0;i<5;i++)
 {
 wgt+=ws[i]*coef[i];
 }
 cout<<wgt<<"\n";
 }
}
```

2024 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2024 Winter) Open - L - Editorial

세 번째 줄에 주어지는 알파벳이 두 번째 줄에 주어지는 알파벳들에 몇 번 등장하는지 세어 출력하면 됩니다. 총 시간 복잡도는 $\mathcal{O}(N)$입니다.