트리의 지름

---

풀이

1. 트리의 지름은 가장 끝에 있는 두 노드 사이의 가중치의 합이다.
2. 어느 한 노드에서 가장 멀리있는점은 지름에 해당하는 노드중 한 노드이다.
3. 그 점에서 가장 멀리있는 노드 사이의 가중치 합을 구하면된다.
4. 즉, dfs를 두번쓰면 된다.

---

vector<pair<int,int>> graph[MAX];

벡터배열+pair가 들어가서 문제를 풀때 햇갈렸다.
graph[0]은 vector<pair<int,int>>를 뜻하므로, graph[0].size()값만큼
pair<int,int>>의 개수를 가지고있다.
graph[0].size() == 2 라면, graph[0] = [{a,b},{x,y}] 이다.
여기서 나오는
graph[v][i].first는 벡터배열중 v번째 벡터에 있는 i번째 원소를 타겟할때 pair의 첫번째 원소를 뜻한다. graph[0][0].first = a, graph[0][1].first = x 이다.

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <string>
#include <string.h>
#include <queue>

using namespace std;
#define endl "\n"

#define MAX 10000+1
int n;
vector<pair<int, int>> graph[MAX];
bool visited[MAX];
int maxWei; // 최대 거리를 측정하기 위한 변수
int endPoint; // 최대 거리에있는 노드를 기억하기 위한 변수

void dfs(int v, int w) {
	visited[v] = true;

	if (maxWei < w)
	{
		endPoint = v;
		maxWei = w;
	}

	for (int i = 0; i < graph[v].size(); i++)
	{
		int nextNode = graph[v][i].first;
		int weight = graph[v][i].second;

		if (visited[nextNode])
		{
			continue;
		}

		dfs(nextNode, w + weight);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//ifstream cin; cin.open("input.txt");

	cin >> n;
	for (int i = 0; i < n-1; i++)
	{
		int x, y, z;
		cin >> x >> y >> z;

		graph[x].push_back({ y,z });
		graph[y].push_back({ x,z });
	}

	dfs(1, 0);

	memset(visited, false, sizeof(visited));
	maxWei = 0;

	dfs(endPoint, 0);
	cout << maxWei;
}

참고

https://codingwell.tistory.com/61 코드 및 풀이 참고