풀이
트리를 일단 나눴다면, 나눠진 후의 모든 컴포넌트에 속한 노드 수는 같아야 한다.
즉, 노드는 n의 약수로만 나눠질 수 있다.
100만 이하 자연수의 약수 개수가 최대 240개니까
O(240*n) 잘 커팅하면 6초 안에 될 거 같은데 안 됨 흠…
아무튼 나이브하게는 안 돌아가므로 조금 더 생각을 해야한다.
트리를 돌며 gcd(서브트리의 노드 개수, n)의 개수를 세어주자.
음… 그냥 코드를 보는 게 더 빠르겠다.
코드
#include <cstdio>
#include <vector>
using namespace std;
int n, cnt[1000001];
vector<int> d, res, gph[1000001];
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
int go(int now, int prv) {
int ret = 1;
for (int nxt : gph[now]) {
if (nxt != prv) ret += go(nxt, now);
}
cnt[gcd(ret, n)]++;
return ret;
}
int main() {
scanf("%d", &n);
for (int i = 1, u, v; i < n; i++) {
scanf("%d %d", &u, &v);
gph[u].emplace_back(v);
gph[v].emplace_back(u);
}
for (int i = 1; i <= n; i++) {
if (!(n%i)) d.emplace_back(i);
}
go(1, 0);
for (int i = 0; i < d.size(); i++) {
for (int j = i + 1; j < d.size(); j++) {
if (!(d[j]%d[i])) cnt[d[i]] += cnt[d[j]];
}
}
for (int i = (int)d.size()-2; i >= 0; i--) {
if (cnt[d[i]] == n/d[i]) printf("%d ", n/d[i]-1);
}
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이