백준 1167 : 트리의 지름 c++

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;

bool visited[100001];
vector<pair<int, int> > v[100001];
int V;
int n[100001];
int maxx;
int last;

void dfs(int a, int leng){
	visited[a] = true;
	bool chk = false;
	for(int i = 0; i < v[a].size(); i++){
		if(!visited[v[a][i].first]){
			chk = true;
		}
	}
	
	if(!chk){
		if(leng > maxx){
			maxx = leng;
			last = a;
		}
		return;	
	} 
	
	for(int i = 0; i < v[a].size(); i++){
		if(!visited[v[a][i].first]){
			visited[v[a][i].first] = true;
			dfs(v[a][i].first, leng+v[a][i].second);
		}	
	}
}

int main(){
	
	ios::sync_with_stdio(false);
	cin.tie(NULL);
    cout.tie(NULL);
    
	cin >> V;
	
	for(int i = 0; i < V; i++){
		cin >> n[i];
		
		int a, b;
		while(true){
			cin >> a;
			if(a == -1)break;
			cin >> b;
			v[n[i]].push_back(make_pair(a, b));
		}
	}

	dfs(n[0], 0);
	memset(visited, 0, 100001*sizeof(bool));
	dfs(last, 0);
	
	cout << maxx;
	
	return 0;
}

알게된 점

처음엔 모든 노드에서 dfs돌려서 했는데 시간초과가 나왔다.

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

아무점에서 최고로 먼 점을 찾는다

그리고 그 점에서 최고로 먼점을 찾으면 트리의 지름이 나온다!

알아두어야겠다..