BOJ 1167 트리의 지름

BOJ 1167 트리의 지름

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

트리, DFS

난이도 MH

트리의 지름이란?

트리의 한 정점(V1)에서 다른 정점(V2) 까지의 거리가 제일 큰 것을 트리의 정점이라 한다.

보통 트리의 지름을 구하는 방법은

아무 정점이나 하나 골라서 가장 거리가 먼 V1을 찾고

그 V1을 이용해 가장 거리가 먼 V2를 찾아 길이를 구하면 트리의 지름이 된다.

#define _CRT_SECURE_NO_WARNINGS 

#include 
#include 
#include 
#include 

using namespace std;

#define MAX_N 100000

int N, A, B, V;

typedef pair PAIR;
vector > input;
bool v1[MAX_N + 1];
bool v2[MAX_N + 1];

PAIR longest(int v, bool* visited)
{
	visited[v] = true;

	PAIR ret = make_pair(0, 0);

	for (int i = 0; i < input[v].size(); i++)
	{
		if (!visited[input[v][i].first])
		{
			PAIR p = longest(input[v][i].first, visited);

			if (ret.second < input[v][i].second + p.second)
			{
				ret.second = input[v][i].second + p.second;
				ret.first = p.first;
			}
		}
	}

	if (ret.first == 0)
		return make_pair(v, 0);
	return ret;
}

int main(int argc, char** argv)
{
#ifdef _WIN32
	freopen("Text.txt", "r", stdin);
#endif

	scanf("%d", &N);

	input = vector >(N + 1);

	for (int i = 1; i <= N; i++)
	{
		scanf("%d", &V);

		while (true)
		{
			scanf("%d", &A);

			if (A == -1)
				break;

			scanf("%d", &B);

			input[V].push_back(make_pair(A, B));
		}

	}

	PAIR p1 = longest(1, v1);
	PAIR p2 = longest(p1.first, v2);
	printf("%d", p2.second);

	return 0;
}