BOJ)14657 준오는 최종인재야!!

문제:icpc.me/14657

문제를 해석해보자면 최대한 많이 문제를 푸는건 결국 주어진 트리를 가중치 없는 그래프에서의 지름에 해당 되는 정점들을 선택하는 경우이다.

하지만 같은 크기를 가지는 지름이 많을 수 있기 때문에 모든 지름을 탐색해야한다.

이를 위하여 지름의 중심이 되는 점을 찾은 뒤 그 점부터 이동 가능한 가장 먼 leaf로의 최단거리를 탐색한 다음 계산해준다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 1e9
using namespace std;
int n, t, a, b, c, r, u, v, res, xx, yy;
vector<vector<pair<int, int>>> vt;
vector<int> dist, pv, xxx, yyy;
vector<pair<int, int>> ans;
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 + 1);
    }
}
void track(int here, int prv) {
    pv[here] = prv;
    for (auto next : vt[here]) {
        if (next.first == prv)continue;
        track(next.first, here);
    }
}
void dfs2(int here, int prv, int dis, int dph) {
    int f = 0;
    for (auto next : vt[here]) {
        if (next.first == prv)continue;
        f = 1;
        dfs2(next.first, here, dis + next.second, dph + 1);
    }
    if (!f) {
        if (dph == r / 2)
            yy = min(yy, dis);
        else if (dph == r / 2 + 1)
            xx = min(xx, dis);
    }
}
int main() {
    scanf("%d%d", &n, &t);
    vt.resize(n + 1);
    for (int i = 0; i < n - 1; i++) {
        scanf("%d%d%d", &a, &b, &c);
        vt[a].push_back({ b,c });
        vt[b].push_back({ a,c });
    }
    dist.assign(n + 1, INF);
    dfs(1, 0);
    v = u, r = 0;
    dist.assign(n + 1, INF);
    dfs(u, 0);
    pv.assign(n + 1, 0);
    track(u, 0);
    int it = r / 2;
    while (it--)
        v = pv[v];
    it = v;
    for (auto next : vt[v]) {
        xx = 1e9;
        yy = 1e9;
        dfs2(next.first, v, next.second, 1);
        if (xx != 1e9)
            xxx.push_back(xx);
        else
            yyy.push_back(yy);
    }
    sort(xxx.begin(), xxx.end());
    sort(yyy.begin(), yyy.end());
    if (r % 2) {
        if (r == 1)
            res = xxx[0];
        else
            res = xxx[0] + yyy[0];
    }
    else
        res = yyy[0] + yyy[1];
    printf("%d\n", res / t + (res%t ? 1 : 0));
    return 0;
}