[Baekjoon - 20614] Tree Product

난이도: Platinum V

 

태그

• Depth First Search
• Dynamic Programming on Tree

 

풀이

1. 트리 \( A \)와 \( B \)에 대해, \( A \times B \)의 지름은?

(\( A \)의 지름) + 2 × (\( B \)의 깊이)가 됩니다.

// \( A \)의 지름의 두 끝점에서 \( B \)를 타고 최대한 많이 내려가는 걸 생각해봅시다.

 

...한 가지 예외가 있는데, \( A \)의 크기가 1일 때입니다.

하지만 크기가 1인 트리는 Tree Product의 항등원이기 때문에 (아무리 곱해도 결과가 바뀌지 않음) 따로 빼놓을 수 있기 때문에, 걱정하지 않아도 됩니다.

 

2. 트리 \( A \)와 \( B \)에 대해, \( A \times B \)의 깊이는?

[1]에서 트리의 지름을 계산하려면, 트리의 깊이가 필요합니다.

 

다행히도, \( A \times B \)의 깊이 역시 간단하게 계산할 수 있으며, 이 값은 (\( A \)의 깊이) + (\( B \)의 깊이)입니다.

// \( A \)에서 최대한 내려간 뒤, \( B \)를 타고 또 최대한 내려가는 걸 생각해봅시다.

 

3. 이게 의미하는 바는?

만약 우리가 \( T_1 \times T_2 \times \ldots \times T_N \)의 순서로 행한다면,

문제에서 알려준 Associative 때문에 \( T_1 \times (T_2 \times \ldots \times T_N) \)으로 볼 수 있습니다.

 

이제 [1]의 식을 써보면, 이 트리의 지름은 (\( T_1 \)의 지름) + 2 × (\( T_2 \times \ldots \times T_N \)의 깊이)이고,

[2]의 식을 써보면, \( T_2 \times \ldots \times T_N \)의 깊이는 (\( T_2 \)의 깊이) + ... + (\( T_N \)의 깊이)가 됩니다.

 

즉, 맨 앞에 오는 트리의 지름과 나머지 트리의 깊이 합만 알고 있으면 최종 트리의 지름을 알 수 있습니다!

맨 앞에 오는 트리를 바꿔가면서, 트리의 깊이 합을 잘 관리하고 있으면 \( O(N) \) 시간에 문제를 풀 수 있습니다.

 

4. 구현 디테일

[1]에서 정점이 1개인 트리는 빼놓기로 했는데, 그렇기 때문에 모든 트리가 정점 1개일 때를 약간 주의해주세요.

 

5. 코드

vector< vector<int> > adj[1000020];
int root[1000020], dep[1000020], dia[1000020];
 
void dfs(int idx, int now, int pre, int dpt){
    dep[idx] = max(dep[idx], dpt);
    for (int nxt : adj[idx][now]){
        if (nxt == pre){ continue; }
        dfs(idx, nxt, now, dpt+1);
    }
}
 
int dis[1000020];
pi2 bfs(const vector< vector<int> >& adj, int st){ int n = adj.size();
    for (int i = 0; i < n; i++){ dis[i] = -1; } dis[st] = 0;
    queue<int> q; q.push(st);
    pi2 res = {st, 0};
    while (!q.empty()){
        int now = q.front(); q.pop();
        res = {now, dis[now]};
        for (int nxt : adj[now]){
            if (dis[nxt] != -1){ continue; }
            dis[nxt] = dis[now]+1; q.push(nxt);
        }
    }
    return res;
}
 
const int INF = 1e9;
 
void Main(){
    int t; cin >> t; while (t--){
        int n; cin >> n;
        int sum = 0;
        for (int i = 1; i <= n; i++){
            int m; cin >> m; adj[i].resize(m);
            for (int v = 0; v < m; v++){
                int w; cin >> w; w--;
                if (w == -1){ root[i] = v; }
                else{
                    adj[i][v].push_back(w); adj[i][w].push_back(v);
                }
            }
            dep[i] = 0; dfs(i, root[i], -1, 0); sum += dep[i];
            dia[i] = bfs( adj[i], bfs(adj[i], root[i]).fr ).sc;
        }
        int mx = 0, mn = INF;
        for (int i = 1; i <= n; i++){
            if (adj[i].size() == 1){ continue; }
            int res = dia[i] + 2*(sum-dep[i]);
            mx = max(mx, res); mn = min(mn, res);
        }
        if (mn == INF){ cout << 0 << ' ' << 0 << endl; }
        else{ cout << mx << ' ' << mn << endl; }
        for (int i = 1; i <= n; i++){ adj[i].clear(); }
    }
}