📝 문제 정보#
번역#
문제#
방향이 없는 간선으로 이루어진 트리가 있으며, 각 노드는 정수 값을 가지고 있습니다. 인접한 두 노드의 값의 최대공약수(GCD)가 $1$보다 엄밀히 클 때, 이 두 노드를 **GCD-조화롭다(GCD-harmonic)**고 합니다.
트리의 임의의 노드 값을 원하는 양의 정수로 변경할 수 있습니다. 이 연산의 비용은 원래 값에 관계없이 새로 설정하는 값과 같습니다. 필요한 만큼 여러 노드의 값을 변경할 수 있으며, 노드 값이 서로 다를 필요는 없습니다.
트리의 모든 인접 노드 쌍이 GCD-조화롭도록 만드는 최소 총 비용은 얼마입니까?
입력#
첫 번째 줄에 정수 $n$ ($2 \leq n \leq 5,000$)이 주어지며, 이는 트리의 노드 수입니다. 트리의 노드는 $1$부터 $n$까지 번호가 매겨져 있습니다.
다음 $n$개의 줄 각각에 정수 $v$ ($1 \le v \le 100$)가 주어집니다. 이는 노드 번호 순서대로의 초기 값이며, 값이 유일할 필요는 없습니다.
다음 $n - 1$개의 줄 각각에 두 정수 $a$와 $b$ ($1 \leq a, b \leq n, a \neq b$)가 주어지며, 이는 노드 $a$와 $b$ 사이의 트리 간선을 나타냅니다. 이 간선들이 트리를 이루는 것이 보장됩니다.
출력#
트리의 모든 인접 노드 쌍을 GCD-조화롭게 만드는 최소 총 비용을 하나의 정수로 출력하십시오.
🧐 관찰 및 접근#
- 어떤 트리가 있고, 간선 양쪽의 정점의 최대공약수가 1이 아니어야한다.
- 일단 예제그림을 그려보자.
- ![[Drawing 2026-02-20 09.13.18.excalidraw]]
- 아하, 루트를 6으로 바꾸면 해결된다.
- 일단 GCD가 1만 아니면 되므로, 어떤 소수 $p$에 대해 생각했다면 $p^2, p^3, \cdots$에 대해서는 생각할 필요가 없다.
- 근데 각 소수에 대해서 다 고려해야할 때가 있나? 루트가 $1$, 밑에 리프들이 $2, 3, 5, 7, 11, \cdots$인 경우를 생각해보자.
- 이때, 루트를 저 소수들의 곱으로 나타내는거보다, 그냥 모든 트리를 $2$로 고정해버리는게 더 싸다.
- 같은 상황에서, 답은 $2n$을 넘길 수 없다. 다시 말해 정점 하나의 값은 $2n \leq 10000$ 이하이다.
- $100$ 이하의 소수의 개수는 25개이다.
- 물론 100이 넘는 소수도 고려할 필요가 없다.
- $10000$ 이하의 Square-Free number은 6084개이다.
- 왠지 이걸로 tree-DP가 가능할 것 같기도 한데.
- $2 \times 3 \times 5 \times 7 \times 11 \times 13 > 10000$이므로, 약수는 최대 5개 존재하니까 전이식은 최대 32번 안쪽인것같다.
- 그러면 $O(n \times 6084 \times 32)$ 정도로 돌지 않을까? 9.7억인데 4초니까 돌만해보인다. 실제로는 더 적을거같기도 하고..
- DP 전이식도 잘 세워보자.
- 루트 기준에서는
- $\text{DP}[cur][cval] = \sum{\min_{nval | cval}{DP[nxt][nval]}}$
- 으로 할 수 있는듯?
- 근데 이게 배수관계로 가면 $2$의 배수인 Square-Free number은 2027개인데, 이래도 시간복잡도가 보장이 되나?
- 루트 기준에서는
- 아 근데, 수들이 $2 - 6 - 3 - 10$ 이런식으로 연결될 수도 있다.. 약수/배수관계로만 생각하는게 조금 곤란하네. 그렇다고 gcd가 1이 아닌 관계의 개수를 세면 너무 많아보인다.
- DP를 두가지로 세워볼까? 결국 $\text{DP}[cur][cval]$을 구했다면, 그 뒤에 갱신할때는 $nval|cval$ 인것들만 세면 되니까, 결국 소수에 대해서만 궁금하다. 저걸 구한 다음에는 소수 $p | cval$들에 대해 최솟값을 갱신해두고, 걔네들을 돌기만 하는거지.
💻 풀이#
- 코드 (C++):
void solve(){
vector<bool> isPrime(101, true);
isPrime[0] = isPrime[1] = false;
rep(i, 2, 101) for(int j = i*i; j < 101; j += i) isPrime[j] = false;
vector<int> primes;
rep(i, 2, 101) if(isPrime[i]) primes.push_back(i);
unordered_map<int, int> primeToIdx;
rep(i, 0, primes.size()) primeToIdx[primes[i]] = i;
vector<int> squareFree;
rep(i, 2, 10001){
bool isSquareFree = true;
for(auto p: primes){
if(p*p > i) break;
if(i % (p*p) == 0){
isSquareFree = false;
break;
}
}
if(isSquareFree) squareFree.push_back(i);
}
unordered_map<int, int> sqfToIdx;
rep(i, 0, squareFree.size()) sqfToIdx[squareFree[i]] = i;
vector<vector<int>> divs(squareFree.size());
rep(i, 0, squareFree.size()) for(auto p: primes) if(squareFree[i] % p == 0){
divs[i].push_back(primeToIdx[p]);
}
int N; cin >> N;
vector<int> V(N);
rep(i, 0, N) cin >> V[i];
rep(i, 0, N) for(auto p: primes) while(V[i] % (p*p) == 0) V[i] /= p;
vector<vector<int>> links(N);
rep(i, 0, N-1){
int u, v; cin >> u >> v;
u--; v--;
links[u].push_back(v);
links[v].push_back(u);
}
vector<int> DP(N, 1e9);
vector<vector<int>> DP2(N, vector<int>(primes.size(), 1e9));
function<void(int, int)> dfs = [&](int cur, int par) {
for(auto nxt: links[cur]) if(nxt != par) dfs(nxt, cur);
rep(i, 0, squareFree.size()){
int cost = 0;
if(V[cur] != squareFree[i]) cost = squareFree[i];
for(auto nxt: links[cur]){
if(nxt == par) continue;
int tmp = 1e9;
for(auto pidx: divs[i]) tmp = min(tmp, DP2[nxt][pidx]);
cost += tmp;
}
for(auto pidx: divs[i]) DP2[cur][pidx] = min(DP2[cur][pidx], cost);
}
DP[cur] = *min_element(all(DP2[cur]));
};
int ans = 1e9;
dfs(0, -1);
cout << DP[0] << "\n";
}