BOJ)13016 내 왼손에는 흑염룡이 잠들어 있다

문제: icpc.me/13016

오랜만에 문제 포스팅을 한다.

문제를 요약하면 한 정점 v에서 다른 정점으로의 최단거리를 dist[i] (i: 1~n) 이라고 했을 때, dist[i]의 최댓값을 모든 정점 v에 대해 구하는 문제이다.

물론 한 정점에서 dist[i]의 최댓값을 구하는건 dfs를 수행하여 쉽게 해결할 수 있지만 모든 정점에 대해 구하게 될 경우 정점의 개수가 5만이므로 시간초과를 보게 될 것이다.

하지만 조금 생각해보면 한 정점에서의 부터 다른 정점으로 부터의 최단 거리 중 최댓값은 트리의 지름의 양 끝 단말 노드 중 하나로의 거리라는 것을 알 수 있다.

(만약 트리 지름의 단말 노드가 아닌 다른 리프로 부터의 거리가 최댓값이라면, 트리의 지름보다 긴 거리가 생긴다는 뜻이므로 모순이된다.)

따라서 트리의 지름의 단말 노드 u,v를 구해준 뒤 u,v로의 거리만 dfs 2번을 수행하여 구해준 뒤 비교하여 출력해주면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
vector<vector<pair<int,int>>> vt;
vector<int> dist;
int n,x,y,z,maxlen,v,u,res[50050];
const int inf=2e9+10;
void dfs(int here,int dis){
    dist[here]=dis;
    if(dist[here]>maxlen){
        maxlen=dist[here];
        u=here;
    }
    for(auto next:vt[here]){
        if(dist[next.first]!=inf)continue;
        dfs(next.first,dis+next.second);
    }
}
int main(){
    scanf("%d",&n);
    vt.resize(n+1);
    for(int i=0;i<n-1;i++){
        scanf("%d%d%d",&x,&y,&z);
        vt[x].push_back({y,z});
        vt[y].push_back({x,z});
    }
    dist.assign(n+1,inf);
    dfs(1,0);
    v=u,maxlen=0;
    dist.assign(n+1,inf);
    dfs(v,0);
    for(int i=1;i<=n;i++)
        res[i]=dist[i];
    dist.assign(n+1,inf);
    dfs(u,0);
    for(int i=1;i<=n;i++)
        printf("%d\n",max(res[i],dist[i]));
    return 0;
}