BOJ 12912 트리 수정

문제 링크입니다.

지름 구하기

트리의 지름은 깊이 우선 탐색을 통해 구할 수 있습니다. 임의의 정점에서 가장 멀리 떨어진 정점이 트리의 지름의 양 끝 정점 중 하나임을 이용합니다.

• 아무 정점이나 하나 골라 그 정점과 가장 멀리 떨어진 정점 하나를 DFS로 찾습니다.
• 앞에서 찾은 그 정점과 가장 멀리 떨어진 다른 정점 하나를 DFS로 찾습니다.
  • 두 단계를 통해 찾은 두 정점이 트리의 지름의 양 끝 점입니다.

지름-지름 구하기

트리에서 간선 하나를 지우면 그래프는 두 개의 트리로 쪼개집니다. 우리는 두 트리를 다시 이어서 지름을 최대화해야 하고, 그렇다면 두 트리의 지름 사이를 잇는 간선을 추가하는 게 좋겠네요.

트리를 이루는 모든 간선에 대해, 그 간선을 지우고 남은 두 트리의 지름을 각각 구한 뒤 지웠던 간선의 가중치를 두 트리의 지름의 합과 더해 그중 최댓값을 고르면 됩니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

int u[2024], v[2024];
ll w[2024];

vector<pll> e[2024];

pll dfs(int now, int pre, int barrier){
	ll node = now; ll w = 0;
	for(auto [nxt, nw] : e[now]){
		if(pre == nxt) continue;
		if(barrier == nxt) continue;
		auto [nnode, nnw] = dfs(nxt, now, barrier);
		nnw += nw;
		if(nnw > w){
			w = nnw;
			node = nnode;
		}
	}
	return {node, w};
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int n; cin >> n;
	for(int i = 1; i < n; i++){
		cin >> u[i] >> v[i] >> w[i];
		e[u[i]].push_back({v[i], w[i]});
		e[v[i]].push_back({u[i], w[i]});
	}
	ll ans = 0;
	for(int i = 1; i < n; i++) ans = max(ans, w[i]+dfs(dfs(u[i], v[i], v[i]).first, v[i], v[i]).second+dfs(dfs(v[i], u[i], u[i]).first, u[i], u[i]).second);
	cout << ans;
}