트리의 지름

Problem link: https://www.acmicpc.net/problem/1167

고민 끝에 재귀 알고리즘을 떠올렸고, 결과적으로는 맞았는데, 뭔가 테스트케이스에 이상이 있는 듯해서 질문을 올려놓았다.

각설하고, 이 문제를 푸는 제대로 된 알고리즘은 아래와 같다.

• 임의의 정점을 x에서 가장 멀리 떨어진 점 y를 찾는다.
• y에서 가장 멀리 떨어진 점 z를 찾는다.
• y-z가 곧 트리의 지름이다.

증명은 아래와 같다.

• 트리의 지름을 알고 있고, 지름의 양 끝점을 u, v라고 해보자.

• 임의의 정점 x에서 가장 멀리 떨어진 점 y를 찾으면 이 y는 u 또는 v임을 보일 것이다.
  (이후의 증명은 쉬우니까 생략)

  • 만약, x가 지름 경로 상에 존재하는 정점이었다면 당연히 y는 u 또는 v로 찾아졌을 것이다.

  • 만약, 그게 아닌 경우라도 마찬가지일 것인데 이는 귀류법으로 증명해보자.

    • y가 u도 아니고 v도 아니고, x가 트리 지름 상에 있는 정점도 아니라고 해보자.
    • dist[x][y] > dist[x][u]가 성립한다는 이야기이다.
    • 이때, 주어진 입력은 트리이므로 x에서 트리 지름 상의 정점으로 가는 길도 반드시 있을 것이다.
    • 그런 점을 p라고 해보자.
    • 그렇다면 이말은 dist[v][y]를 p-x를 이용함으로써 dist[u][v]보다 더 크게 만들수 있다는 이야기이다.
    • 이는 가정에 모순이다(dist[u][v]는 트리 지름이어야 함).

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int kMaxV = 100000;

int V;

vector<pair<int, int> > AL[kMaxV];

vector<bool> VISIT_1ST(kMaxV, false);
vector<bool> VISIT_2ND(kMaxV, false);
vector<bool> VISIT_3RD(kMaxV, false);

vector<int> DIST_1ST(kMaxV, 0);
vector<int> DIST_2ND(kMaxV, 0);
vector<int> DIST_3RD(kMaxV, 0);

void Path(const int here, vector<bool>& visit, vector<int>& dist)
{
  visit[here] = true;

  for (const auto& neighbor : AL[here])
  {
    const int there = neighbor.second;
    const int weight = neighbor.first;

    if (!visit[there])
    {
      dist[there] = dist[here] + weight;
      Path(there, visit, dist);
    }
  }
}

int Solve(void)
{
  Path(0, VISIT_1ST, DIST_1ST);

  int far_vtx = 0;
  int far_dist = DIST_1ST[far_vtx];

  for (int v = 0; v < V; ++v)
  {
    if (DIST_1ST[v] > far_dist)
    {
      far_vtx = v;
      far_dist = DIST_1ST[v];
    }
  }

  Path(far_vtx, VISIT_2ND, DIST_2ND);

  int far_vtx_2 = far_vtx;
  int far_dist_2 = DIST_2ND[far_vtx_2];

  for (int v = 0; v < V; ++v)
  {
    if (DIST_2ND[v] > far_dist_2)
    {
      far_vtx_2 = v;
      far_dist_2 = DIST_2ND[v];
    }
  }

  Path(far_vtx_2, VISIT_3RD, DIST_3RD);

  return DIST_3RD[far_vtx];
}

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read Input
  cin >> V;
  for (int it = 0; it < V; ++it)
  {
    int src;
    cin >> src;

    while (true)
    {
      int dst, weight;
      cin >> dst;

      if (dst == -1)
      {
        break;
      }

      cin >> weight;

      AL[src - 1].emplace_back(weight, dst - 1);
    }
  }

  // Solve
  cout << Solve() << '\n';

  return 0;
}