BOJ 1167 - 트리의 지름

문제 링크 : www.acmicpc.net/problem/1167

문제 태그

DFS

문제 풀이

트리의 한 정점에서 가장 먼 정점을 잡는다. 그러면 그 정점을 트리의 지름의 한쪽 끝이 된다. 따라서 찾은 정점에서 시작하여 가장 먼 정점까지의 거리를 구하면 그 거리가 트리의 지름이 된다. 

- 임의의 한 점에서 가장 먼 점을 잡으면 그 점은 항상 트리의 지름의 한 쪽 끝이 되는가?

아니라고 해보자. 아래의 그림에서 초록이 주황, 노랑보다 길어야 하는데, 그럼 주황-노랑으로 이어진 길이 지름인 것에 모순이다. 따라서 위의 가설은 참이다.

따라서 풀이는 정당하고, 어떤 한 점에서 나머지 모든 점까지의 거리를 구하면 되는데, 이는 다익으로도 할 수 있지만, 트리에서는 dfs로 간단하게 해결할 수 있다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
 
#define ff first
#define ss second
#define ep emplace_back
#define eb emplace
#define pb push_back
 
ll arr[1010101];
vector<pii> v[1010101];
ll dis[1010101];
 
void dfs(ll x){
    for(auto k:v[x]){
        if(dis[k.ss]) continue;
        dis[k.ss]=k.ff+dis[x];
        dfs(k.ss);
    }
}
 
 
int main(){
    ll i,j,k,l,m,n;
    scanf("%lld",&n);
    for(i=1;i<=n;i++){
        scanf("%lld",&m);
        ll a,b;
        scanf("%lld",&a);
        while(a!=-1){
            scanf("%lld",&b);
            v[m].pb({b,a});
            scanf("%lld",&a);
        }
    }
    dfs(1);
    dis[1]=1;
    ll mx=0;
    ll mk=0;
    for(i=1;i<=n;i++){
        if(mx<dis[i]){
            mx=dis[i];
            mk=i;
        }
    }
    for(i=1;i<=n;i++)
        if(i!=mk) dis[i]=0;
 
    dfs(mk);
 
    ll ans=0;
    for(i=1;i<=n;i++)
        ans=max(ans,dis[i]);
    printf("%lld",ans-dis[mk]);
}