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;
}