블로그 옮겼습니다
우선 이 문제를 풀기 위해서 한가지 선행 지식이 필요하다. N개의 노드를 가진 트리에서 모든 정점 쌍의 거리의 합을 O(N)에 구할 수가 있는데 size(i) = i번 노드를 루트로 갖는 서브트리의 노드의 수. 로 정의하여 재귀적으로 모든 노드에 대해 구하면서 각 간선을 지나는 경로의 수를 dfs로 구하는것이다. 이 전, 전 포스트에 설명이 되어있다. 하지만 이 문제는 점프 거리 k 라는 입력이 주어져서 한번에 k개의 간선을 뛰어넘을 수가 있고, 단순히 모든 정점쌍 사이의 거리의 합이 아니라 모든 정점 쌍 사이의 경로를 가기위한 점프 횟수의 합을 요구한다. 그렇기 때문에 최대 점프거리 k가 3일때, 거리가 3인 경로는 3이 아니라 1이 더해져야하고 4인 경로는 4가 아니라 2가 더해져야하는 식이다. 여기..
이 문제는 N개의 노드를 가지고 간선에 가중치가 있는 트리에서 중앙 정점이라는 것을 찾아서 이 중앙 정점에서 다른 정점까지의 모든 거리의 합을 구하는 문제이다.중앙 정점의 정의는 어떤 한 점에서 다른 모든 정점까지의 거리의 합이 최소가 되는 점이다. 처음에 트리의 중심과 헷갈려서 트리의 중심으로 풀 뻔 했는데 잘 생각해 보면 트리의 중심은 어떤 한 점에서 다른 모든 정점까지의 거리의 최대값이 최소가 되는 점이기 때문에 확실히 다른 개념이다. 그렇다면 이 중앙 정점이라는 것은 어떻게 구할까? naive 하게는 각 N개의 정점에서부터 BFS나 DFS를돌려서 한 점에서 다른 모든 점까지의 거리의 합을 구하고 이 값을 바탕으로 최소값을 갱신해 나가는 O(N^2) 의 방법이 있을 것이다. 하지만 N이 10000 ..
naive 하게 모든 노드쌍간의 거리의 총합을 구한다고 하면 총 N개의 노드에 대해 DFS 혹은 BFS를 돌려서 O(N^2) 에 구하는 것이지만 N이 좀더 커지만 사용할 수가 없다.이 때 발상을 조금 전환해서 모든 가능한 경로상에 각각의 간선이 총 몇번이나 포함되는지를 세어주면 이 것의 총합이 우리가 구하고자 하는 답이 될 것이다.그렇다면 트리에서 루트 노드를 제외한 다른 모든 노드들은 하나의 부모가 있으므로 부모와 연결된 간선을 하나씩 가질 것이므로 루트를 제외한 하나의 노드는 각각 하나의 간선과 짝지어질 것이다. 그렇다면 루트 노드를 제외한 각각의 노드에 대해 자신의 부모와 연결된 간선을 지나는 모든 경로의 가지수를 계산하여 누적해 준다면 답이 될것인데 이것은 어떻게하냐면, size(i) 를 i번 노..