11064번: Diameter

https://www.acmicpc.net/problem/11064

#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int t, n, d;
int main() {
    for (scanf("%d", &t); t--;) {
        vector<pair<int, int> > adj[40001];
        priority_queue<pair<int, int> > pq;
        int r = 0, t = 0, cnt = 0, ind[40001] = {};
        scanf("%d%d", &n, &d);
        for (int i = 1, x, y, z; i < n; i++) {
            scanf("%d%d%d", &x, &y, &z);
            adj[x].push_back({ y,z });
            adj[y].push_back({ x,z });
            r += z;
            ind[x]++;
            ind[y]++;
        }
        for (int i = 1; i <= n; i++) if (ind[i] == 1) pq.push({ -adj[i][0].second,i }), cnt++;
        for (;;) {
            int h = pq.top().second, dis = -pq.top().first;
            pq.pop();
            if (2 * dis >= d) {
                printf("%.1lf\n", r - (d / 2.0 - t) * cnt);
                break;
            }
            r -= (dis - t)*cnt--;
            if (cnt == 1) {
                puts("0.0");
                break;
            }
            ind[h]--;
            for (auto u : adj[h]) if (--ind[u.first] == 1) {
                for (auto v : adj[u.first]) if (ind[v.first]) pq.push({ -dis - v.second,u.first }), cnt++;
            }
            t = dis;
        }
    }
    return 0;
}

1167번: 트리의 지름

https://www.acmicpc.net/problem/1167


$O(n)$

http://codedoc.tistory.com/240

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int n, r;
vector<pair<int, int> > adj[100001];
int f(int h, int p) {
    int m1 = 0, m2 = 0;
    for (auto it : adj[h]) if (it.first^p) {
        m2 = max(m2, f(it.first, h) + it.second);
        if (m1 < m2) swap(m1, m2);
    }
    r = max(r, m1 + m2);
    return m1;
}
int main() {
    scanf("%d", &n);
    for (int i = 1, a, b, c; i <= n; i++) {
        scanf("%d", &a);
        while (scanf("%d", &b), b^-1) {
            scanf("%d", &c);
            adj[a].push_back({ b,c });
        }
    }
    f(1, 0);
    printf("%d", r);
    return 0;
}

8872번: 빌라봉

https://www.acmicpc.net/problem/8872


$O(n+m)$

트리에서 나머지 지점까지의 거리의 최댓값이 최소가 되는 지점을 중심이라 하고 그 값을 반지름이라 하자.
반지름이 최대인 트리의 중심에 나머지 트리의 중심을 이어주면 된다.

따라서 답은 다음 가능한 경우 중 최댓값이다.

1. 트리의 최대 지름
2. 최대 반지름 + 두번째 반지름 + L
3. 두번째 반지름 + 세번째 반지름 + L*2

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MXN = 1e5;
int n, m, l, d[MXN], ck[MXN], r;
vector<pair<int, int> > adj[MXN];
void f(int h) {
    ck[h] = 1;
    for (auto it : adj[h]) if (!ck[it.first]) {
        f(it.first);
        d[h] = max(d[h], d[it.first] + it.second);
    }
}
int g(int h, int pl) {
    int m1 = pl, m2 = 0, t = 2e9;
    ck[h] = 0;
    for (auto it : adj[h]) if (ck[it.first]) {
        m2 = max(m2, d[it.first] + it.second);
        if (m1 < m2) swap(m1, m2);
    }
    r = max(r, m1 + m2);
    for (auto it : adj[h]) if (ck[it.first]) t = min(t, g(it.first, (m1 == d[it.first] + it.second ? m2 : m1) + it.second));
    return min(m1, t);
}
int main() {
    scanf("%d%d%d", &n, &m, &l);
    for (int i = 0, x, y, z; i < m; i++) {
        scanf("%d%d%d", &x, &y, &z);
        adj[x].push_back({ y,z });
        adj[y].push_back({ x,z });
    }
    for (int i = 0; i < n; i++) if (!ck[i]) f(i);
    int m[3] = { -1000000000,-1000000000 };
    for (int i = 0; i < n; i++) if (ck[i]) {
        m[2] = max(m[2], g(i, 0));
        for (int j = 3; --j;) if (m[j] > m[j - 1]) swap(m[j], m[j - 1]);
    }
    printf("%d", max({ r,m[0] + m[1] + l,m[1] + m[2] + l * 2 }));
    return 0;
}

4009번: 순찰

https://www.acmicpc.net/problem/4009

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MXN = 1e5;
int n, k, d[MXN + 1], l[MXN + 1], r;
vector<int> adj[MXN + 1];
void f(int h, int p) {
    int m1 = 0, m2 = 0;
    for (auto it : adj[h]) if (it^p) {
        f(it, h);
        l[h] = max(l[h], l[it]);
        m2 = max(m2, d[it] + 1);
        if (m1 < m2) swap(m1, m2);
    }
    if (m2) l[h] = max(l[h], m1 + m2);
    d[h] = m1;
}
void g(int h, int p, int pd, int pl) {
    int l1 = pl, l2 = 0;
    pair<int, int> c[4] = { { pd,p }, };
    for (auto it : adj[h]) if (it^p) {
        if (c[3] < make_pair(d[it] + 1, it)) {
            c[3] = { d[it] + 1,it };
            for (int i = 3; i; i--) if (c[i] > c[i - 1]) swap(c[i], c[i - 1]);
        }
        l2 = max(l2, l[it]);
        if (l1 < l2) swap(l1, l2);
    }
    r = max({ r,pd + d[h],l[h] });
    if (k == 2) {
        r = max(r, pl + l[h]);
        if (c[3].first) r = max(r, c[0].first + c[1].first + c[2].first + c[3].first);
    }
    for (auto it : adj[h]) if (it^p) {
        int td1 = 0, td2 = -1e9, tl = l[it] ^ l1 ? l1 : l2;
        for (int i = 0; i < 4; i++) if (c[i].second^it&&c[i].second) {
            if (!td1) td1 = c[i].first;
            else if (td2 < 0) td2 = c[i].first;
        }
        g(it, h, td1 + 1, max(td1 + td2, tl));
    }
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0, x, y; i < n - 1; i++) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    f(1, 0);
    g(1, 0, 0, 0);
    printf("%d", n * 2 + k - r - 2);
    return 0;
}

2970번: 두더지

https://www.acmicpc.net/problem/2970


$O(n)$

먼저, 트리의 지름(트리 상에서 가장 먼 두 정점의 경로)을 구한다.
지름의 끝 정점을 s1, s2라 하자.
s1과 s2를 잇는 경로상의 한 간선을 지워야 한다. 그러지 않는다면, 지름의 값이 가장 먼 두 정점의 거리가 될 것이기 때문이다.
간선을 하나 지웠다고 해보자. 문제는 s1을 포함하는 트리의 지름과 s2를 포함하는 트리의 지름에 의해 답이 결정된다.
s1-a1-a2-a3- ... - an-s2 (ai는 가지를 가질 수도 있다.) 모양에서
s1 ~ ai, ai~s2 트리마다의 지름을 구해야 한다.
이는 s1,s2를 시작 정점으로 하는 dfs 탐색을 이용해 해결할 수 있다.
이에 대해 간략하게 말하면 탐색에서 자신을 끝으로 하는 사슬의 최대 길이와 자식들의 지름을 가지고 갱신시키면 된다.
(본 블로그 내의 트리의 지름 1번 풀이를 참고하자. http://codedoc.tistory.com/240)
a(i-1) 과 ai를 끊었을 때의 최소 거리는 다음 세 값 중 최댓값이다.
1. s1~a(i-1) 상의 지름
2. ai~s2 상의 지름
3. s1~a(i-1) 반지름 + ai~s2 반지름 + 1
최댓값이 가장 작을 때가 답이다.
자를 곳을 결정했다면 그 간선을 제거하고 나눠진 트리에서 각각 중심점을 찾고 이으면 된다.

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N = 3e5;
vector<int> adj[MAX_N + 1];
int n, maxi, t, ck[MAX_N + 1];
int vis[MAX_N], vck;
void dfs1(int h, int p, int dep, int v) {
    if (dep > maxi) maxi = dep, t = h;
    ck[h] = 1;
    if (v != -1 && !vck) vis[dep] = h;
    if (h == v) vck = 1;
    for (auto it : adj[h])
        if (!ck[it]) dfs1(it, h, dep + 1, v);
    ck[h] = 0;
}
int l[2][MAX_N + 1];
int dfs2(int h, int p, int idx) {
    int m1 = 0, m2 = 0;
    for (auto it : adj[h]) {
        if (it == p) continue;
        m2 = max(m2, dfs2(it, h, idx) + 1);
        if (m1 < m2) swap(m1, m2);
        l[idx][h] = max(l[idx][h], l[idx][it]);
    }
    l[idx][h] = max(l[idx][h], m1 + m2);
    return m1;
}
int main() {
    scanf("%d", &n);
    for (int i = 0, x, y; i < n - 1; i++) {
        scanf("%d %d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    int s1, s2, idx, res = 0x7fffffff;
    maxi = -1; dfs1(1, -1, 0, -1); s1 = t;
    maxi = -1; dfs1(s1, -1, 0, -1); s2 = t;
    dfs2(s2, -1, 0);
    dfs2(s1, -1, 1);
    maxi = -1; dfs1(s1, -1, 0, s2);
    for (int i = 1, tl; i <= maxi; i++) {
        tl = max({ (l[0][vis[i - 1]] + 1) / 2 + (l[1][vis[i]] + 1) / 2 + 1,
            l[0][vis[i - 1]],l[1][vis[i]] });
        if (res > tl) res = tl, idx = i;
    }
    s1 = vis[idx - 1]; s2 = vis[idx];
    int h1, h2, r1, r2;
    ck[s2] = 1;
    maxi = -1; dfs1(s1, -1, 0, -1); h1 = t;
    maxi = -1; dfs1(h1, -1, 0, -1); h2 = t;
    maxi = -1; vck = 0; dfs1(h1, -1, 0, h2); r1 = vis[maxi / 2];
    ck[s2] = 0; ck[s1] = 1;
    maxi = -1; dfs1(s2, -1, 0, -1); h1 = t;
    maxi = -1; dfs1(h1, -1, 0, -1); h2 = t;
    maxi = -1; vck = 0; dfs1(h1, -1, 0, h2); r2 = vis[maxi / 2];
    printf("%d\n%d %d\n%d %d", res, s1, s2, r1, r2);
    return 0;
}

1967번: 트리의 지름

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


1. 트리 DP

$O(n)$

rooted tree를 만든다.
x번 노드가 루트인 서브트리 내에서 트리의 지름 다음 중 최댓값이다.
1. x번 노드의 자식이 루트인 서브트리 내에서 트리의 지름
2. 리프 노드에서 x번 노드까지의 두 최장경로 길이 합

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
const int MAX_N = 1e4;
vector<pair<int, int> > adj[MAX_N + 1];
int n, res;
int dfs(int h) {
    int r1 = 0, r2 = 0;
    for (auto it : adj[h]) {
        r2 = max(r2, it.second + dfs(it.first));
        if (r1 < r2) swap(r1, r2);
    }
    res = max(res, r1 + r2);
    return r1;
}
int main() {
    scanf("%d", &n);
    for (int i = 0, x, y, z; i < n - 1; i++) {
        scanf("%d %d %d", &x, &y, &z);
        adj[x].push_back({ y,z });
    }
    dfs(1);
    printf("%d", res);
    return 0;
}

2. DFS 두 번

$O(n)$

아무 정점 하나를 시작점으로 잡아 그 지점으로부터 가장 먼 지점을 찾는다.
이 지점은 트리의 지름에서 양 끝 지점 중 하나가 된다.
마찬가지로 이 지점을 시작점으로 잡아 그 지점으로부터 가장 먼 지점을 찾는다.
이 지점은 지름의 양 끝 지점 중 나머지 하나가 된다.

증명은
http://blog.myungwoo.kr/112

#include<cstdio>
#include<vector>
using namespace std;
int res, n, idx;
vector<pair<int, int> > adj[10001];
void f(int h, int p, int d) {
        if (d > res) res = d, idx = h;
        for (auto it : adj[h]) if (it.first^p) f(it.first, h, d + it.second);
}
int main() {
        scanf("%d", &n);
        for (int i = 0, x, y, z; i < n - 1; i++) {
                scanf("%d%d%d", &x, &y, &z);
                adj[x].push_back({ y,z });
                adj[y].push_back({ x,z });
        }
        f(1, 0, 0);
        f(idx, 0, 0);
        printf("%d", res);
        return 0;
}