import java.io.*; import java.util.*; public class Main { public static void main(String[] args) { FastReader fr = new FastReader(); int N = fr.nextInt(); int[] energy = new int[N]; for (int i = 0; i < N; i++) { energy[i] = fr.nextInt(); } int[][] graph = new int[N][N]; Pair[][] sparse = new Pair[15][N]; for (int i = 0; i < N - 1; i++) { int a = fr.nextInt() - 1; int b = fr.nextInt() - 1; int cost = fr.nextInt(); graph[a][b] = graph[b][a] = cost; } Queue queue = new LinkedList<>(); queue.offer(0); boolean[] visited = new boolean[N]; while (!queue.isEmpty()) { int cur = queue.poll(); visited[cur] = true; for (int i = 0; i < N; i++) { if (graph[cur][i] != 0 && !visited[i]) { sparse[0][i] = new Pair(cur, graph[cur][i]); queue.offer(i); } } } for (int i = 1; i < 15; i++) { for (int j = 0; j < N; j++) { try { Pair cur = sparse[i - 1][j]; int cost = cur.cost + sparse[i - 1][cur.next].cost; sparse[i][j] = new Pair(sparse[i - 1][cur.next].next, cost); } catch (Exception ignored) {} } } int[] pos = new int[N]; for (int i = 0; i < N; i++) { pos[i] = i; } for (int i = 14; i >= 0; i--) { for (int j = 0; j < N; j++) { if (sparse[i][j] != null) { if (sparse[i][j].cost <= energy[j]) { pos[j] = sparse[i][j].next; energy[j] -= sparse[i][j].cost; } } } } // for (int i = 0; i < 15; i++) { // System.out.println(Arrays.toString(sparse[i])); // } for (int p : pos) { System.out.println(p + 1); } } static class Pair { int next, cost; Pair(int next, int cost) { this.next = next; this.cost = cost; } public String toString() { return "(" + next + ", " + cost + ")"; } } public static class FastReader { BufferedReader br; StringTokenizer st; public FastReader() { br = new BufferedReader(new InputStreamReader(System.in)); } public FastReader(String s) throws FileNotFoundException { br = new BufferedReader(new FileReader(new File(s))); } String next() { while (st == null || !st.hasMoreElements()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } } }

제출 #38529

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: