📝 문제 정보#
🧐 관찰 및 접근#
- 가중치 없는 트리인줄 알고, 당연히 지름-1이 답이 아닌가? 했더니 가중치가 있었다
- 가중치가 있는 트리라면, 우리가 원래 쓰던 DFS두번이라는 방법은 쉽지 않을것같다
- 가장 긴 트리의 지름과, 두번째로 긴 트리의 지름이 아예 관계 없는 곳에 있을 수도 있지 않을까?
- 아닌가?
- ![[Drawing 2026-01-25 09.41.32.excalidraw.png]]
- 트리의 지름과 두번째 트리의 지름이 끝 정점을 공유하지 않는다고 하자. 그렇다면, 위 그림과 같이 압축해서 나타낼 수 있다.
- 이 때, $a + b = D_1 \geq c + d = D_2$라 하자.
- 일반성을 잃지 않고 $a \geq b, c \geq d$라 하자.
- 서로 공유하는 정점 하나가 있는 경우
- $a + c \geq D_1/2 + D_2/2 \geq D_2$
- 이므로, a와 c를 지나는 경로가 우리가 가정한 두번째 지름보다 더 크거나 같다.
- 더 큰 경우 모순이고
- 같은 경우 $a+c$를 두번째 지름으로 택해도 아무 문제가 없다.
- 서로 공유하는 정점이 없는경우 (다른 서브트리에 나타낼 수 있는 경우)
- $a + c + e + f \geq D_1/2 + D_2/2 + e + f > D_2$
- 이므로, $D_2$의 경로는 두번째 트리의 지름이 아니다.
- 이 때, $a + b = D_1 \geq c + d = D_2$라 하자.
- 따라서, 트리의 두번째 지름의 한 끝점은 트리의 지름의 한 끝점과 같다.
- DFS를 돌려서 트리의 지름 양 끝 점을 찾고, 거기서부터 두번째지름을 한번씩 찾아주자.
💻 풀이#
- 코드 (C++):
vector<pii> dfs(int cur, int par){
vector<pii> v;
v.push_back({0, cur});
for(auto [nxt, w]: links[cur]){
if(nxt == par) continue;
auto nv = dfs(nxt, cur);
rep(i, 0, min(2, (int)nv.size())){
v.push_back({nv[i].first + w, nv[i].second});
}
sort(all(v), greater<pii>());
while(v.size() > 2) v.pop_back();
}
return v;
}
void solve(){
cin >> N;
rep(i, 0, N-1){
int u, v, w; cin >> u >> v >> w;
links[u].push_back({v, w});
links[v].push_back({u, w});
}
int L = dfs(1, -1)[0].second; // 트리의 지름의 한쪽 끝
int ans = 0;
auto ret = dfs(L, -1);
ans = max(ans, ret[1].first); // 두번째 트리의 지름 후보 1
int R = ret[0].second; // 트리의 지름의 다른쪽 끝
ret = dfs(R, -1);
ans = max(ans, ret[1].first); // 두번째 트리의 지름 후보 2
cout << ans << "\n";
}