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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <cstdio>
#include <vector>
#include <queue>
#include <functional>
 
typedef long long int ll;
 
using namespace std;
 
const int N = 100001;
 
void change(int& x, int& y) {
    int k;
    k = x;
    x = y;
    y = k;
}
vector <int> v[N];
priority_queue <int, vector<int>, greater<int> > pq;
int n, ar[N], dist[N], ep, ep_v, ind[N], dist_i[N];
 
int main(void)
{
    int a, b;
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++)
        scanf("%d", &ar[i]);
    for (int i = 1; i < n; i++) {
        scanf("%d %d", &a, &b);
        if (a > b)
            change(a, b);
        v[b].push_back(a);
        ind[a]++;
    }
 
    for (int i = 1; i <= n; i++) {
        if (ind[i] == 0) {
            pq.push(i);
            dist[i] = ar[i];
            dist_i[i] = i;
        }
    }
    while (!pq.empty()) {
        int e = pq.top();
        pq.pop();
        for (int i = 0; i < v[e].size(); i++) {
            int to = v[e][i];
            ind[to]--;
            if (dist[e] + ar[to] >= dist[to] && dist_i[to] < dist_i[e]) {
                dist[to] = dist[e] + ar[to];
                dist_i[to] = dist_i[e];
            }
            if (ind[to] == 0) pq.push(to);
        }
    }
    
    printf("%d %d", dist_i[1], dist[1]);
    return 0;
}
cs



서강대 3번 위상으로 풀었는데 칼같이 10점뜸


이거 예선부터 광탈할 삘임....