[BOJ 1167] 트리의 지름

1167번: 트리의 지름

 

널리(?) 알려진 것과 달리 dfs 한 번으로 해결할 수 있다. 사실 그 방법을 몰라서 이렇게 풀었다.

 

풀이

 

임의의 루트를 하나 잡고 트리를 구축했다고 생각하자. 트리의 지름을 만드는 두 노드의 공통 조상은 트리 위의 노드 중 하나이기 때문에, 모든 노드에 대하여 그 노드를 공통 조상으로 하는 두 노드의 최대 거리를 시도해보면 된다. 이를 위해 필요한 정보는 각 서브 트리의 최대 깊이와 여러 서브 트리 중 첫 번째와 두 번째로 깊은 깊이이고, 이는 dfs를 돌면서 잘 관리해줄 수 있다.

 

코드

 

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> ad[100001];
int mx;
int dfs(int u,int p) {
	int mx1=0,mx2=0;
	for(auto &[v,d] : ad[u]) if(v^p){
		int dep=d+dfs(v,u);
		if(dep>=mx1) mx2=mx1, mx1=dep;
		else if(dep>mx2) mx2=dep;
	}
	mx=max(mx,mx1+mx2);
	return mx1;
}
int main()
{
	cin.tie(0)->sync_with_stdio(0);
	int n; cin >> n;
	for(int i=1;i<=n;i++){
		int u,v,d; cin >> u;
		while(1){
			cin >> v; if(!~v) break;
			cin >> d;
			ad[u].push_back({v,d});
		}
	}
	dfs(1,0); cout << mx;
}