트리의 지름

트리에서의 지름이란, 트리에서 가장 멀리 떨어진 두 점 사이의 거리를 구하는 문제이다.

2가지 솔루션이 있고, 2개 모두 알아두도록 하자.

 

SOL 1)

전체적인 알고리즘은, 

1. 임의의 한 점으로부터 제일 멀리 떨어진 점을 잡고, (A)

2. 그 점으로부터 제일 멀리 떨어진 점을 잡는다. (B)

이때 A, B는 지름을 구성하는 요소이다.

=> dfs 2번으로 답을 구한다.

 

만약 A가 지름을 구성하는 두 점중 하나가 맞다면 2는 자명하다.

따라서 A가 지름을 구성하는 점임을 보여 보자.

 

(귀류법) 임의의 정점에서 제일 멀리 떨어진 점 X를 잡았는데, 그 점이 지름 A, B 모두 아니라 하자.

위 그림에서 루트 R과 제일 멀리 떨어진 점 X를 골랐다 하자. (X!=A, X!=B)

1. 지름이 루트를 지난다면 A-R-B 꼴일 것이고, B를 X로 바꾸면 A-R-X 가 더 길다. (모순)

2. 지름이 루트를 지나지 않는다 하면 A, B의 LCA C가 존재하며, A-C(p), C-B (q)에 의해 p+q 가 지름이 된다. 그러나, 위 그림의 식에 의하여 A-C-B 보다 B-R-X 의 경로가 길이가 더 길게 된다. (모순)

 

증명이 복잡하긴 하지만, 코드는 dfs 두번만 하면 되기 때문에 매우 간단하다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int n;
vector<pii> adj[MAXN+10];

int vis[MAXN+10];

void dfs(int now, int dep)
{
    vis[now]=dep;
    int i;
    for(i=0; i<adj[now].size(); i++) if(vis[adj[now][i].first]==-1) dfs(adj[now][i].first, dep+adj[now][i].second);
}

int main()
{
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    int i, j;

    scanf("%d", &n);
    for(i=1; i<n; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }

    memset(vis, -1, sizeof(vis));
    dfs(1, 0);

    int a=-1, b;
    for(i=1; i<=n; i++) if(a<vis[i]) a=vis[i], b=i;

    memset(vis, -1, sizeof(vis));
    dfs(b, 0);

    int ans=-1;
    for(i=1; i<=n; i++) ans=max(ans, vis[i]);

    printf("%d", ans);

    return 0;
}

시간 복잡도 : $O(N)$

 

SOL 2)

이번에는 다음을 이용하자.

1. 지름은 무조건 잎~잎으로 이어진다. (루트의 차수가 1인 경우 잎으로 취급)

2. 만약 루트를 지난다면 루트의 자식들로 만들어진 서브트리의 높이 중 최대 2개 선택해 더한다.

=> 트리 DP

 

이와 같이 생각하면 dfs함수가 각 서브트리에서의 최대 높이를 반환해 주면 답을 계속 갱신할 수 있다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int n;
vector<pii> adj[MAXN+10];

int ans;

int dfs(int now)
{
    int a=0, b=0, ret=0;

    int i;
    for(i=0; i<adj[now].size(); i++)
    {
        int x=dfs(adj[now][i].first)+adj[now][i].second;
        ret=max(ret, x);

        if(x>a) b=a, a=x;
        else if(x>b) b=x;
    }
    ans=max(ans, a+b);
    return ret;
}

int main()
{
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    int i, j;

    scanf("%d", &n);
    for(i=1; i<n; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        adj[a].push_back({b, c});
    }

    dfs(1);
    printf("%d", ans);
    return 0;
}

시간 복잡도 : $O(N)$

 

문제 : https://www.acmicpc.net/problem/1967