[Baekjoon - 3973] Time To Live

난이도: Gold III

 

태그

• Diameter of a Tree

 

풀이

1. 답의 Upper Bound는?

ceil( (트리의 지름) / 2 )입니다.

트리의 지름을 정확히 절반으로 나누는 어떤 점을 선택했을 때, 그 점에서부터 지름의 두 끝점까지의 거리죠.

 

2. 근데 그 Upper Bound보다 더 잘 할 수 있나?

트리의 지름의 두 끝점을 \( v, w \)라고 해봅시다.

그럼, 임의의 정점 \( u \)에 대해 \( d(v, u) + d(u, w) \ge d(v, w) \)가 됩니다.

 

즉, \( u \)로 무슨 정점을 잡아도 \( d(v, u) \)랑 \( d(u, w) \) 둘 중 하나는 UpperBound 이상의 값을 가지게 되니,

[1]에서 구한 UpperBound가 실제로 최적의 값임을 알 수 있습니다.

 

3. 코드

트리의 지름 찾는 건 dfs를 해도 되고, tree dp를 해도 됩니다.

int n;
vector<int> adj[100020];
 
const int INF = 1e9;
pi2 dis[100020];
void bfs(int st){
    for (int i = 1; i <= n; i++){ dis[i] = {INF, 0}; }
    dis[st] = {0, 0};
    queue<int> q; q.push(st);
    while (!q.empty()){
        int now = q.front(); q.pop();
        for (int nxt : adj[now]){
            if (dis[nxt].fr != INF){ continue; }
            dis[nxt] = {dis[now].fr+1, now}; q.push(nxt);
        }
    }
}