[BOJ 1167] 트리의 지름

[BOJ 1167] 트리의 지름

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

풀이

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

코드

#include using namespace std; vector> 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; }

from http://heejayaa.tistory.com/117 by ccl(A) rewrite - 2021-10-24 01:01:01