A building has n circuit breakers numbered 1 to n.
They are joined by n − 1 wires, and a wire "a b" joins breaker a and breaker b.
Following the wires you can get from any breaker to every other breaker.
Breaker 1 is the top breaker, connected to the power plant.
Of two breakers joined by a wire, the one nearer to breaker 1 is the 'upper breaker' and the other is the 'lower breaker'. Which of a and b in the input is the upper one is not fixed.
Breaker i has a device attached that uses uᵢ of electricity, and the capacity of the breaker is cᵢ.
The amount Lᵢ flowing through breaker i is uᵢ plus the L of every lower breaker joined directly to breaker i by a wire that has not tripped.
If Lᵢ is greater than cᵢ, breaker i trips. If Lᵢ equals cᵢ, it does not trip.
The L of a tripped breaker is not added to the L of its upper breaker. So whether breakers trip is decided from the bottom breakers upwards.
A breaker has power only if neither it nor any breaker on the way from it to breaker 1 has tripped.
A caretaker starts at breaker 1 and checks breakers as follows.
If the current breaker has tripped, the caretaker writes down its number and does not go below it.
Otherwise the caretaker checks its lower breakers one at a time from the smallest number, and after choosing one, checks everything below it in the same way before moving on to the next lower breaker.
On the first line print the number of breakers that have power.
On the second line print L₁. Even if breaker 1 trips, L₁ is the value given by the rule above.
On the third line print the numbers the caretaker wrote, in the order written, separated by single spaces. If no number was written, print -.
Input
The first line has n, the second line u₁ … uₙ, the third line c₁ … cₙ, and each of the next n − 1 lines has a and b. Numbers on a line are separated by one space. 1 ≤ n ≤ 9,000, 0 ≤ uᵢ ≤ 1,000,000,000, 0 ≤ cᵢ ≤ 10,000,000,000,000 (10 trillion), 1 ≤ a, b ≤ n, a ≠ b. Every breaker can be reached from breaker 1 over at most 1,200 wires. All are integers
Output
First line: the number of breakers with power. Second line: L₁ (digits only, no commas). Third line: the numbers the caretaker wrote, or -
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
This takes two depth-first searches (DFS). One goes all the way down and adds up L on the way back (the lower ones must be settled first), and one goes down from the top counting where power arrives. The wires do not say which end is upper, so link both ways and go down everywhere except 'where you just came from'. In the example breaker 7 trips (5 > 4), so L of breaker 3 is 5 + 40 = 45, which is more than 44, so breaker 3 trips too. Breaker 4 also trips (30 > 25), so L of breaker 2 is 10 + 20 = 30 and L of breaker 1 is 30. Trap one: add the share of a tripped breaker to the one above and breaker 2 becomes 60 and trips, and then breaker 1 trips as well. Trap two: breaker 5 holds because 20 = 20. Write >= and breaker 5 trips too. Trap three: the caretaker does not go below a tripped breaker. Keep going and breaker 7 is written too, giving 4 3 7. Trap four: lower breakers go in number order. Take them in input order and you get 3 4. In JS and TS sort() without a compare function compares as strings, so 10 comes before 9; write sort((x, y) => x - y). Python list.sort(), Java Collections.sort, C# List.Sort(), C++ std::sort, C qsort and Craykon list.Sort() compare numbers by size. Trap five: L grows up to 9 trillion. Java and C# int silently give a wrong number and in C and C++ it is undefined behaviour, so use long / long long. Python has no limit, and JS, TS and Craykon are exact up to 2^53. Trap six: recursion depth. Python's default limit is 1,000, so an input of depth 1,200 stops with RecursionError; raise it with sys.setrecursionlimit or use your own stack. The other languages are fine at this depth, but that does not mean they have no limit (Craykon: a few thousand levels). A Craykon function is made directly with a name and parentheses, like load(v, upper) { … return total; }.
Pythonmain.py · 55 lines
import syssys.setrecursionlimit(5000) # 기본 한도 1,000으로는 깊이 1,200까지 못 내려간다def main(): data = sys.stdin.buffer.read().split() n = int(data[0]) use = [0] + [int(x) for x in data[1:1 + n]] cap = [0] + [int(x) for x in data[1 + n:1 + 2 * n]] near = [[] for _ in range(n + 1)] # 전선은 방향 없이 주어진다 pos = 1 + 2 * n for _ in range(n - 1): a, b = int(data[pos]), int(data[pos + 1]) pos += 2 near[a].append(b) near[b].append(a) for v in range(1, n + 1): near[v].sort() # 번호가 작은 아래쪽 차단기부터 본다 tripped = [False] * (n + 1) def load(v, parent): """v를 지나는 전기의 양을 돌려준다. 아래쪽부터 정해야 하므로 내려갔다 올라오면서 더한다.""" total = use[v] for w in near[v]: if w != parent: below = load(w, v) if not tripped[w]: # 내려간 차단기 아래로는 전기가 흐르지 않는다 total += below tripped[v] = total > cap[v] return total lit = 0 fix = [] def walk(v, parent): """1번에서 내려가며 전기가 오는 곳을 세고, 맨 먼저 올릴 차단기를 적는다.""" nonlocal lit if tripped[v]: fix.append(v) # 이 아래는 어차피 전기가 안 오니 내려가지 않는다 return lit += 1 for w in near[v]: if w != parent: walk(w, v) root_load = load(1, 0) walk(1, 0) print(lit) print(root_load) print(" ".join(map(str, fix)) if fix else "-")main()
JavaScriptmain.js · 54 lines
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const use = [0];const cap = [0];for (let v = 1; v <= n; v++) { use.push(data[v]); cap.push(data[n + v]);}// 전선은 방향 없이 주어진다const near = Array.from({ length: n + 1 }, () => []);for (let i = 0; i < n - 1; i++) { const a = data[1 + 2 * n + 2 * i]; const b = data[2 + 2 * n + 2 * i]; near[a].push(b); near[b].push(a);}// 번호가 작은 아래쪽 차단기부터 본다. sort()는 그냥 쓰면 문자열로 견주니 비교 함수를 준다for (const list of near) list.sort((x, y) => x - y);const tripped = new Array(n + 1).fill(false);// v를 지나는 전기의 양. 아래쪽부터 정해야 하므로 내려갔다 올라오면서 더한다function load(v, parent) { let total = use[v]; // 9조까지 커져도 2^53 안이라 정확하다 for (const w of near[v]) { if (w !== parent) { const below = load(w, v); if (!tripped[w]) total += below; // 내려간 차단기 아래로는 전기가 흐르지 않는다 } } tripped[v] = total > cap[v]; return total;}let lit = 0;const fix = [];// 1번에서 내려가며 전기가 오는 곳을 세고, 맨 먼저 올릴 차단기를 적는다function walk(v, parent) { if (tripped[v]) { fix.push(v); // 이 아래는 어차피 전기가 안 오니 내려가지 않는다 return; } lit++; for (const w of near[v]) { if (w !== parent) walk(w, v); }}const rootLoad = load(1, 0);walk(1, 0);console.log(lit);console.log(rootLoad);console.log(fix.length > 0 ? fix.join(" ") : "-");
TypeScriptmain.ts · 56 lines
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const use: number[] = [0];const cap: number[] = [0];for (let v = 1; v <= n; v++) { use.push(data[v]); cap.push(data[n + v]);}// 전선은 방향 없이 주어진다const near: number[][] = Array.from({ length: n + 1 }, (): number[] => []);for (let i = 0; i < n - 1; i++) { const a = data[1 + 2 * n + 2 * i]; const b = data[2 + 2 * n + 2 * i]; near[a].push(b); near[b].push(a);}// 번호가 작은 아래쪽 차단기부터 본다. sort()는 그냥 쓰면 문자열로 견주니 비교 함수를 준다for (const list of near) list.sort((x, y) => x - y);const tripped: boolean[] = new Array<boolean>(n + 1).fill(false);// v를 지나는 전기의 양. 아래쪽부터 정해야 하므로 내려갔다 올라오면서 더한다function load(v: number, parent: number): number { let total = use[v]; // 9조까지 커져도 2^53 안이라 정확하다 for (const w of near[v]) { if (w !== parent) { const below = load(w, v); if (!tripped[w]) total += below; // 내려간 차단기 아래로는 전기가 흐르지 않는다 } } tripped[v] = total > cap[v]; return total;}let lit = 0;const fix: number[] = [];// 1번에서 내려가며 전기가 오는 곳을 세고, 맨 먼저 올릴 차단기를 적는다function walk(v: number, parent: number): void { if (tripped[v]) { fix.push(v); // 이 아래는 어차피 전기가 안 오니 내려가지 않는다 return; } lit++; for (const w of near[v]) { if (w !== parent) walk(w, v); }}const rootLoad = load(1, 0);walk(1, 0);console.log(lit);console.log(rootLoad);console.log(fix.length > 0 ? fix.join(" ") : "-");
JavaMain.java · 62 lines
import java.io.*;import java.util.*;public class Main { static long[] use, cap; static List<List<Integer>> near = new ArrayList<>(); static boolean[] tripped; static int lit = 0; static StringBuilder fix = new StringBuilder(); // v를 지나는 전기의 양. 아래쪽부터 정해야 하므로 내려갔다 올라오면서 더한다 static long load(int v, int parent) { long total = use[v]; // 합이 9조까지 커지므로 int로는 모자란다 for (int w : near.get(v)) { if (w != parent) { long below = load(w, v); if (!tripped[w]) total += below; // 내려간 차단기 아래로는 전기가 흐르지 않는다 } } tripped[v] = total > cap[v]; return total; } // 1번에서 내려가며 전기가 오는 곳을 세고, 맨 먼저 올릴 차단기를 적는다 static void walk(int v, int parent) { if (tripped[v]) { if (fix.length() > 0) fix.append(' '); fix.append(v); // 이 아래는 어차피 전기가 안 오니 내려가지 않는다 return; } lit++; for (int w : near.get(v)) { if (w != parent) walk(w, v); } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); use = new long[n + 1]; cap = new long[n + 1]; tripped = new boolean[n + 1]; StringTokenizer st = new StringTokenizer(br.readLine()); for (int v = 1; v <= n; v++) use[v] = Long.parseLong(st.nextToken()); st = new StringTokenizer(br.readLine()); for (int v = 1; v <= n; v++) cap[v] = Long.parseLong(st.nextToken()); // 용량은 10조까지라 long으로 읽는다 for (int v = 0; v <= n; v++) near.add(new ArrayList<>()); for (int i = 0; i < n - 1; i++) { // 전선은 방향 없이 주어진다 st = new StringTokenizer(br.readLine()); int a = Integer.parseInt(st.nextToken()), b = Integer.parseInt(st.nextToken()); near.get(a).add(b); near.get(b).add(a); } for (List<Integer> list : near) Collections.sort(list); // 번호가 작은 아래쪽 차단기부터 본다 long rootLoad = load(1, 0); walk(1, 0); System.out.println(lit); System.out.println(rootLoad); System.out.println(fix.length() > 0 ? fix.toString() : "-"); }}
C#Main.cs · 71 lines
using System;using System.Collections.Generic;class Program{ static long[] use = Array.Empty<long>(), cap = Array.Empty<long>(); static List<int>[] near = Array.Empty<List<int>>(); static bool[] tripped = Array.Empty<bool>(); static int lit = 0; static readonly List<int> fix = new List<int>(); // v를 지나는 전기의 양. 아래쪽부터 정해야 하므로 내려갔다 올라오면서 더한다 static long Load(int v, int parent) { long total = use[v]; // 합이 9조까지 커지므로 int로는 모자란다 foreach (int w in near[v]) { if (w != parent) { long below = Load(w, v); if (!tripped[w]) total += below; // 내려간 차단기 아래로는 전기가 흐르지 않는다 } } tripped[v] = total > cap[v]; return total; } // 1번에서 내려가며 전기가 오는 곳을 세고, 맨 먼저 올릴 차단기를 적는다 static void Walk(int v, int parent) { if (tripped[v]) { fix.Add(v); // 이 아래는 어차피 전기가 안 오니 내려가지 않는다 return; } lit++; foreach (int w in near[v]) { if (w != parent) Walk(w, v); } } static void Main() { var data = Console.In.ReadToEnd().Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(data[0]); use = new long[n + 1]; cap = new long[n + 1]; tripped = new bool[n + 1]; near = new List<int>[n + 1]; for (int v = 0; v <= n; v++) near[v] = new List<int>(); for (int v = 1; v <= n; v++) { use[v] = long.Parse(data[v]); cap[v] = long.Parse(data[n + v]); // 용량은 10조까지라 long으로 읽는다 } for (int i = 0; i < n - 1; i++) // 전선은 방향 없이 주어진다 { int a = int.Parse(data[1 + 2 * n + 2 * i]), b = int.Parse(data[2 + 2 * n + 2 * i]); near[a].Add(b); near[b].Add(a); } foreach (var list in near) list.Sort(); // 번호가 작은 아래쪽 차단기부터 본다 long rootLoad = Load(1, 0); Walk(1, 0); Console.WriteLine(lit); Console.WriteLine(rootLoad); Console.WriteLine(fix.Count > 0 ? string.Join(" ", fix) : "-"); }}
C++main.cpp · 65 lines
#include <algorithm>#include <iostream>#include <vector>using namespace std;vector<long long> use, cap;vector<vector<int>> near_; // near_[v] = v와 전선으로 이어진 차단기들vector<bool> tripped;int lit = 0;vector<int> fix;// v를 지나는 전기의 양. 아래쪽부터 정해야 하므로 내려갔다 올라오면서 더한다long long load(int v, int parent) { long long total = use[v]; // 합이 9조까지 커지므로 int로는 모자란다 for (int w : near_[v]) { if (w != parent) { long long below = load(w, v); if (!tripped[w]) total += below; // 내려간 차단기 아래로는 전기가 흐르지 않는다 } } tripped[v] = total > cap[v]; return total;}// 1번에서 내려가며 전기가 오는 곳을 세고, 맨 먼저 올릴 차단기를 적는다void walk(int v, int parent) { if (tripped[v]) { fix.push_back(v); // 이 아래는 어차피 전기가 안 오니 내려가지 않는다 return; } lit++; for (int w : near_[v]) { if (w != parent) walk(w, v); }}int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; use.assign(n + 1, 0); cap.assign(n + 1, 0); for (int v = 1; v <= n; v++) cin >> use[v]; for (int v = 1; v <= n; v++) cin >> cap[v]; near_.assign(n + 1, {}); for (int i = 0; i < n - 1; i++) { // 전선은 방향 없이 주어진다 int a, b; cin >> a >> b; near_[a].push_back(b); near_[b].push_back(a); } for (auto &list : near_) sort(list.begin(), list.end()); // 번호가 작은 아래쪽 차단기부터 본다 tripped.assign(n + 1, false); long long rootLoad = load(1, 0); walk(1, 0); cout << lit << "\n" << rootLoad << "\n"; if (fix.empty()) { cout << "-\n"; } else { for (size_t i = 0; i < fix.size(); i++) cout << fix[i] << (i + 1 < fix.size() ? ' ' : '\n'); } return 0;}
Cmain.c · 81 lines
#include <stdio.h>#include <stdlib.h>static long long *use, *cap;static int *start, *near; // near[start[v]] … near[start[v + 1] - 1] = v와 전선으로 이어진 차단기들static char *tripped;static int lit = 0;static int *fix, fixCount = 0;static int byNumber(const void *x, const void *y) { return *(const int *)x - *(const int *)y;}// v를 지나는 전기의 양. 아래쪽부터 정해야 하므로 내려갔다 올라오면서 더한다static long long load(int v, int parent) { long long total = use[v]; // 합이 9조까지 커지므로 int로는 모자란다 for (int i = start[v]; i < start[v + 1]; i++) { int w = near[i]; if (w != parent) { long long below = load(w, v); if (!tripped[w]) total += below; // 내려간 차단기 아래로는 전기가 흐르지 않는다 } } tripped[v] = total > cap[v]; return total;}// 1번에서 내려가며 전기가 오는 곳을 세고, 맨 먼저 올릴 차단기를 적는다static void walk(int v, int parent) { if (tripped[v]) { fix[fixCount++] = v; // 이 아래는 어차피 전기가 안 오니 내려가지 않는다 return; } lit++; for (int i = start[v]; i < start[v + 1]; i++) { if (near[i] != parent) walk(near[i], v); }}int main(void) { int n; if (scanf("%d", &n) != 1) return 0; use = malloc((n + 1) * sizeof(long long)); cap = malloc((n + 1) * sizeof(long long)); for (int v = 1; v <= n; v++) scanf("%lld", &use[v]); for (int v = 1; v <= n; v++) scanf("%lld", &cap[v]); // 용량은 10조까지라 %lld로 읽는다 // 전선은 방향 없이 주어진다. 먼저 차단기마다 전선 수를 세어 자리를 잡고, 그 자리에 채운다 int edges = n - 1; int *a = malloc((edges + 1) * sizeof(int)), *b = malloc((edges + 1) * sizeof(int)); start = calloc(n + 2, sizeof(int)); for (int i = 0; i < edges; i++) { scanf("%d %d", &a[i], &b[i]); start[a[i] + 1]++; start[b[i] + 1]++; } for (int v = 1; v <= n + 1; v++) start[v] += start[v - 1]; near = malloc((2 * edges + 1) * sizeof(int)); int *fill = malloc((n + 2) * sizeof(int)); for (int v = 0; v <= n + 1; v++) fill[v] = start[v]; for (int i = 0; i < edges; i++) { near[fill[a[i]]++] = b[i]; near[fill[b[i]]++] = a[i]; } // 번호가 작은 아래쪽 차단기부터 본다 for (int v = 1; v <= n; v++) qsort(near + start[v], start[v + 1] - start[v], sizeof(int), byNumber); tripped = calloc(n + 1, 1); fix = malloc((n + 1) * sizeof(int)); long long rootLoad = load(1, 0); walk(1, 0); printf("%d\n%lld\n", lit, rootLoad); if (fixCount == 0) { printf("-\n"); } else { for (int i = 0; i < fixCount; i++) printf(i > 0 ? " %d" : "%d", fix[i]); printf("\n"); } free(use); free(cap); free(a); free(b); free(start); free(near); free(fill); free(tripped); free(fix); return 0;}
Craykonmain.cray · 72 lines
// v를 지나는 전기의 양. 아래쪽부터 정해야 하므로 내려갔다 올라오면서 더한다전기량(v, 위){ total = use[v]; // 9조까지 커져도 2^53 안이라 정확하다 foreach (w in near[v]) { if (w != 위) { below = 전기량(w, v); if (!tripped[w]) { total += below; } } } tripped[v] = total > cap[v]; return total;}// 1번에서 내려가며 전기가 오는 곳을 세고, 맨 먼저 올릴 차단기를 적는다걷기(v, 위){ if (tripped[v]) { fix.Add(v + 1); // 이 아래는 어차피 전기가 안 오니 내려가지 않는다 return; } lit += 1; foreach (w in near[v]) { if (w != 위) { 걷기(w, v); } }}n = Console.ReadLine().ToNumber();// 목록은 10,000칸까지라 차단기 번호에서 1을 빼 0번부터 둔다use = Console.ReadNumbers();cap = Console.ReadNumbers();near = [];for (v = 0; v < n; v++){ near.Add([]);}for (i = 0; i < n - 1; i++){ 선 = Console.ReadNumbers(); near[선[0] - 1].Add(선[1] - 1); near[선[1] - 1].Add(선[0] - 1);}foreach (list in near){ list.Sort(); // 번호가 작은 아래쪽 차단기부터 본다}tripped = NewList(n, false);lit = 0;fix = [];rootLoad = 전기량(0, -1);걷기(0, -1);Console.WriteLine(lit);Console.WriteLine(rootLoad);if (fix.Count > 0){ Console.WriteLine(fix);}else{ Console.WriteLine("-");}