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 行
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 行
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 行
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 行
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 行
#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 行
#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 行
// v를 지나는 전기의 양. 아래쪽부터 정해야 하므로 내려갔다 올라오면서 더한다전기량(v, 위){ total = use[v]; // 9조까지 커져도 2^53 안이라 정확하다 それぞれ (w の中 near[v]) { もし (w != 위) { below = 전기량(w, v); もし (!tripped[w]) { total += below; } } } tripped[v] = total > cap[v]; 返す total;}// 1번에서 내려가며 전기가 오는 곳을 세고, 맨 먼저 올릴 차단기를 적는다걷기(v, 위){ もし (tripped[v]) { fix.追加(v + 1); // 이 아래는 어차피 전기가 안 오니 내려가지 않는다 返す; } lit += 1; それぞれ (w の中 near[v]) { もし (w != 위) { 걷기(w, v); } }}n = コンソール.行読み().数に();// 목록은 10,000칸까지라 차단기 번호에서 1을 빼 0번부터 둔다use = コンソール.数読み();cap = コンソール.数読み();near = [];繰り返す (v = 0; v < n; v++){ near.追加([]);}繰り返す (i = 0; i < n - 1; i++){ 선 = コンソール.数読み(); near[선[0] - 1].追加(선[1] - 1); near[선[1] - 1].追加(선[0] - 1);}それぞれ (list の中 near){ list.並べ替え(); // 번호가 작은 아래쪽 차단기부터 본다}tripped = 新リスト(n, 偽);lit = 0;fix = [];rootLoad = 전기량(0, -1);걷기(0, -1);コンソール.書く(lit);コンソール.書く(rootLoad);もし (fix.個数 > 0){ コンソール.書く(fix);}でなければ{ コンソール.書く("-");}