BOJ13016: 내 왼손에는 흑염룡이 잠들어 있다

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

  • 일단 Edge마다 목적지에서 갈 수 있는 거리의 최댓값을 저장하는 식의 DP로 풀었다.
  • 시간복잡도는 대충 3*N 정도 되는듯.
  • 다른사람들이 푼 것을 보면, 지름을 구해서 양 지름의 끝과의 거리가 최대거리중 하나라는 원리를 위해 풀었다.
  • 여튼 위의 사실을 잘 알아두는게 좋을듯.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;

struct Edge {
  int v, c, far;
};

class Tree {
  int N;
  vector<vector<Edge>> adj;
public:
  Tree(int n): N(n), adj(n+1) {}
  void input();
  int dfs(int u, int p);
};

void Tree::input() {
  for(int i = 0; i < N-1; i++) {
    int u, v, c;
    scanf("%d%d%d", &u, &v, &c);
    adj[u].push_back({v,c,-1});
    adj[v].push_back({u,c,-1});
  }
}

int Tree::dfs(int u, int p) {
  int ans = 0;
  for (auto &[v, c, far]: adj[u]) {
    if(p == v) continue;
    if(far == -1)
      far = c + dfs(v, u);
    ans = max(ans, far);
  }
  return ans;
}

int main() {
  int N;
  scanf("%d", &N);
  Tree tree(N);
  tree.input();
  for(int i = 1; i <= N; i++)
    printf("%d\n", tree.dfs(i, -1));
}