[백준] 13016 내 왼손에는 흑염룡이 잠들어 있다

전에  weeklyps 에서 트리의 지름을 공부할 배운 방법을 이용했다!

자세한 설명은 weeklyps에 있는 트리의 지름을 보는게 빠를듯.. ㅎㅎㅎ

정점 x를 기준으로 x의 서브트리에 속하는 최장거리, 안속하는 최장거리를 구해서 비교해주면 far 배열을 채울 수 있다..!

서브트리 속하는건 쉬워서 바로 구할 수 있다 트리의 깊이를 구하듯이 구하면 된다

속하지 않는 경우에는 다시 또 경우를 나눠서 구하면 된다...!

자세한 설명은 weeklyps 꼭 가보시길..! 저도 3번읽음 ㅎㅎ

다들 열공~~!

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
#define MAXN 50050
bool check[MAXN];
int dist[MAXN], dist2[MAXN], far[MAXN],n;
vector<vector<pair<int, int>>> Graph;
 
void dist_dfs(int x) {
    check[x] = true;
    dist[x] = dist2[x] = 0;
    for (int i = 0; i < Graph[x].size(); i++) {
        int next = Graph[x][i].first;
        int cost = Graph[x][i].second;
        if (check[next]) continue;
        dist_dfs(next);
        if (dist[x] < dist[next] + cost) {
            dist2[x] = dist[x];
            dist[x] = dist[next] + cost;
        }
        else if (dist2[x] < dist[next] + cost) dist2[x] = dist[next] + cost;
    }
}
void far_dfs(int x, int parent_far) {
    check[x] = true;
    far[x] = max(dist[x], parent_far);
    for (int i = 0; i < Graph[x].size(); i++) {
        int next = Graph[x][i].first;
        int cost = Graph[x][i].second;
        if (check[next]) continue;
        if (dist[x] == dist[next] + cost) far_dfs(next, max(parent_far + cost, dist2[x]+cost));
        else far_dfs(next, max(parent_far + cost, dist[x] + cost));
    }
}
int main() {
    scanf(" %d", &n);
    Graph.resize(n);
    for (int i = 0; i < n-1; i++) {
        int u, v, w; scanf(" %d %d %d", &u, &v, &w);
        u--; v--;
        Graph[u].push_back({ v,w });
        Graph[v].push_back({ u,w });
    }
    dist_dfs(0);
    memset(check, 0, sizeof(check));
    far_dfs(0, 0);
    for (int i = 0; i < n; i++) printf("%d\n", far[i]);
}