트리의 지름3 Educational #56 D - GCD counting (트리(숲) 지름, 소인수분해) https://codeforces.com/contest/1101/problem/D 소인수분해 시간복잡도를 잘못 파악하고 있었다. 루트n인줄 알았는데 소인수분해는 loglogn이다. (에라토스가 루트n이다) 트리 지름 구하는 방법은 알고 있었지만 숲에서 최대 지름을 구하는 것을 O(n)에 할 방법을 생각하지 못했다. 같은 시간복잡도를 갖는 코드라도 시간제한이 빡빡해서 최적화를 해줘야 한다. (난이도에 비해 푼 사람이 적은 이유인듯) 단일 트리와 다른 특별한 알고리즘을 사용하진 않는다. 한 점 잡고 제일 먼 점 u와 u에서 제일 먼 점 v와의 거리를 모든 트리에 대해 구하면 된다. 하나의 트리에 대해 최대 지름을 구한 후, 방문처리를 위한 vst배열을 초기화하지 않고 다음 트리에 대해 최대 지름을 구하는 부.. 2020. 3. 13. BOJ 1967 - 트리의 지름 https://www.acmicpc.net/problem/1967 제목이 곧 내용인 문제 트리의 지름을 구하라 https://suuntree.tistory.com/171아이디어에 대한 추가설명 임의의 점에서 제일 먼 점 u와 u에서 제일 먼 점 v사이의 길이를 구하면 된다. 어떤 점에서 제일 긴 곳까지의 길이는 어떻게 구할까? 가중치가 없는 트리에선 dfs의 깊이가 곧 길이가 된다. 이 문제는 가중치가 있는 그래프이므로 1대신 w 더해주면 된다. 모든 정점에서 이 길이의 최대를 찾으면 된다. dfs 깊이를 효과적으로 유지하려면 함수에 깊이를 의미하는 파라미터를 추가해주면 된다. dfs(u, prv, d)꼴로 한 번의 dfs로 가장 먼 점과 그때의 거리를 구할 수 있다. int n, dst, st; vec.. 2020. 2. 8. FORTRESS - 요새 (트리) https://algospot.com/judge/problem/read/FORTRESS 트리의 지름을 구하는 문제. 임의의 한 점에서 가장 먼 점u, u에서 가장 먼 점v에 대해 u~v거리구하면된다. 서로가 서로에게 포함되거나 포함하는 원들이 최대 100개 주어진다.(겹치거나 접하는 경우 없음) 이때 임의의 두 점 사이에 건너야 하는 벽의 최대 개수를 구해라. 큰 원u가 작은원 v를 포함하는 것을 u->v라 할때 전체 형태는 트리의 형태가 된다. 간선을 이어줄때, 예를들어 a->b->c 인 경우 a->c를 잇지 않도록 주의한다. 반지름을 기준으로 오름차순 정렬하여 적절히 처리해주면 된다. 그리고 트리의 지름을 구하면 된다. 간선을 이어주는 부분 for (int i = 0,x,y,r; i < n; i++).. 2020. 2. 8. 이전 1 다음
