트리의 이심률,지름,반지름

트리에서 존재하는 한 정점 v에서의 이심률(eccentricity)이란 v가 속한 트리내의 모든 정점 u에 대해 max(dist(v,u))를 의미한다.

트리에서의 반지름은 트리내의 모든 정점 v에 대해서 이심률이 최소가 되는 v의 이심률이고

트리에서의 지름은 트리내의 모든 정점 v에 대해서 이심률이 최대가 되는 v의 이심률이다.

간단하게 정리하면 v의 이심률은 v에서 가장 먼 정점까지의 거리로 정의되며

트리의 지름은 트리 내부에서 가장 먼 두점 사이의 거리이며

트리의 반지름은 각 정점들에서의 가장 먼거리들 중 최소가 되는 거리이다.

트리의 지름을 구하는 방법은 익히 잘알려져있는 방법으로 임의의 정점에서 v에서 dfs를 통하여 이심률을 구하고 해당 이심률의 단말에 해당되는 정점 u에서 다시 dfs를 통하여 이심률을 구하면 그게 트리의 지름이 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define INF 987654321
using namespace std;
int n, x, y, z, u, v, r;
vector<int> dist;
vector<vector<pair<int, int>>> vt;
void dfs(int here, int dis) {
    dist[here] = dis;
    if (dist[here] > r) {
        r = 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, r = 0;
    dist.assign(n + 1, INF);
    dfs(u, 0);    //u와 v에 트리의 지름의 단말노드가 담기게 됨
    printf("%d\n", r);
    return 0;
}

트리의 지름의 중요한 성질중 하나로는 트리의 지름을 이루는 두 단말노드를 u,v라고 했을 때

트리 내부의 임의의 정점 x의 이심률은 max(dist(u,x),dist(v,x))가 된다.

반지름에 대해서 이야기를 하자면

반지름은 항상 트리의 지름의 경로에 존재한다. 그리고 지름을 결정하는 정점이 여러개 존재한다 하더라도 아무 정점이나 잡고 그 경로를 확인해주면 반지름을 얻을 수 있다.

따라서 우리는 지름을 결정하는 u,v를 이용하여 반지름을 쉽게 구할 수 있다.

우선 지름이 r이라고 가정하면 반지름 g가 될 수 있는 후보는 u,v를 연결하는 경로상의 정점 x에 대해

모든 x에 대한 max(r-dist(u,x),dist(u,x)))값의 최솟값이 될 것이다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define INF 987654321
using namespace std;
int n, x, y, z, u, v, r, g;
vector<int> dist, back;
vector<vector<pair<int, int>>> vt;
void dfs(int here, int dis) {
    dist[here] = dis;
    if (dist[here] > r) {
        r = dist[here];
        u = here;
    }
    for (auto next : vt[here]) {
        if (dist[next.first] != INF)continue;
        dfs(next.first, dis + next.second);
        back[next.first] = here;    //경로를 저장
    }
}
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 });
    }
    back.assign(n + 1, 0);
    dist.assign(n + 1, INF);
    dfs(1, 0);
    v = u, r = 0;
    back.assign(n + 1, 0);
    dist.assign(n + 1, INF);
    dfs(v, 0);    //u와 v에 트리의 지름의 단말노드가 담기게 됨
    printf("%d\n", r);//지름
    int it = u;
    g = INF;
    while (it) {
        int rad = max(dist[it], r - dist[it]);
        g = min(g, rad);
        it = back[it];
    }
    printf("%d\n", g);//반지름
    return 0;
}