14657 준오는 최종인재야!!

14657 준오는 최종인재야!! https://www.acmicpc.net/problem/14657

트리에서 임의의 한 정점을 선택하고 그 정점에서 최대로 갈 수 있는 정점의 갯수중 그 정점들을 
지나면서의 cost합의 최소값을 구하는 문제이다.

한마디로 트리의 지름만큼 갈 수 있는 지점중 최소의 cost합을 구하는 거다.

트리의 지름은 DFS 2번으로 구할 수 있는데 이 과정에서 최소의 cost합도 구할 수 있다.

다음과 같은 트리가 있다고 하자.
답은 4가 나와야 한다. (최대 5개의 정점을 지남, 5->7 or 7->5) 

DFS(1)을 시작하면 가장 많은 정점을 지나면서 cost가 작은 도착정점을 저장한다. (root)

DFS(root)를 시작해서 가장 많은 정점을 지나면서 cost가 가장 작은 값이 답이다.
5->1로 가는것도 가장 많은 정점을 지나지만 cost는 5->7로 가는것이 가장 작다.

#include <cstdio> #include <vector> #include <algorithm> using namespace std; int N, T; bool visit[50001]; vector<pair<int, int>> adj[50001]; int root, max_size, min_cost; void dfs(int here, int cnt , int cost) {     if (max_size < cnt) {         root = here;         max_size = cnt;         min_cost = cost;     }     else if (max_size == cnt) {         if (min_cost > cost) {             root = here;             max_size = cnt;             min_cost = cost;         }     }     for (auto n : adj[here]) {         int next = n.second;         if (!visit[next]) {             visit[next] = true;             dfs(next, cnt + 1, cost + n.first);         }     } } int main() {     scanf("%d%d", &N, &T);     for (int n = 0;n < N - 1;n++) {         int u, v, d;         scanf("%d%d%d", &u, &v, &d);         adj[u].push_back({ d,v });         adj[v].push_back({ d,u });     }     max_size = 1, min_cost = 0;     visit[1] = true;     dfs(1, 1, 0);     max_size = 1, min_cost = 0;     fill(visit + 1, visit + N + 1, false);     visit[root] = true;     dfs(root, 1, 0);     printf("%d\n", min_cost % T == 0 ? min_cost / T : min_cost / T + 1);     return 0; } Colored by Color Scripter

cs