이 문제는 간단한(주최측에 따르면) 그래프 문제로 대회 때는 아홉 팀이 풀었답니다. ABDE 다음으로 풀만한 문제였습니다.

트리, original 서버의 위치, 서버의 범위 k가 주어집니다. 모든 단말 노드와 서버의 거리가 k이하가 되도록 최소 개수의 서버를
놓는 문제입니다.

저는 이 문제를 그리디로 풀었습니다. 서버 S를 root로 해서 트리를 늘어뜨리고(?), 서버가 필요한 클라이언트에 최대한 멀리 서버를 놓습니다. root를 시작으로 DFS를 한번 돌면서 클라이언트와의 거리, 서버와의 거리 정보를 자식 노드로부터 읽어와 현재
노드에 서버를 놓을지 결정합니다.

슈더 코드를 보고 트리를 그려서 적용해보시면 어떤 방법인지 알 수 있을 겁니다. 그림은 문제에 있는 예제를 다시 그린 것이고,
빨간 숫자는 리턴 값입니다.

DFS를 한번 돌면 끝나기 때문에 시간 복잡도는 O(n)이 됩니다.

DFS (v)
  현재 노드가 단말 노드면 return 1
  mn ← ∞
  mx ← -∞
  for v와 연결된 모든 노드 u에 대해
    u가 v의 부모면 continue
    dis ← DFS(u)
    mn ← min(mn, dis)
    mx ← max(mx, dis)
  if abs(mn) > mx then return mn+1    // 예제에서 3번 노드에 해당합니다. 10번 노드와 4번 노드의 거리가 k이하입니다.
  if mx = k and v != S then    // 단말 노드와의 거리가 k가 되면 서버를 놓습니다. 다만 현재 노드가 S면 놓을 필요가 없겠죠?
    cnt ← cnt + 1     // 답을 1 증가시킵니다.
    return -k    // 음수값은 서버가 놓였다는 것을 의미합니다.
  if mx = 0 then return 0    // 서버를 놓으면 값이 음수에서 1씩 올라가게 되는데 그 값이 0이 되면 계속 0으로 유지합니다. 사향 트리를 생각해보면 이 조건이 필요하다는 것을 알 수 있습니다.
  return mx+1    // 현재 노드에 서버를 놓지 않을 경우, 단말 노드와의 거리를 1 늘린 값을 리턴합니다.