Submission #286721


Source Code Expand

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	@SuppressWarnings("unchecked")
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int x = sc.nextInt()-1;
		int[] h = new int[n];
		for(int i=0;i<n;i++) {
			h[i] = sc.nextInt();
		}
		ArrayList<Integer>[] edge = new ArrayList[n];
		for(int i=0;i<n;i++) {
			edge[i] = new ArrayList<>();
		}
		for(int i=0;i<n-1;i++) {
			int a = sc.nextInt()-1;
			int b = sc.nextInt()-1;
			edge[a].add(b);
			edge[b].add(a);
		}
		int ans = Integer.MAX_VALUE;
		ans = Math.min(ans, dfs(-1,x,edge,h));
		if (ans < 0) {
			ans = 0;
		}
		System.out.println(ans);
	}

	public static int dfs(int parent,int v,ArrayList<Integer>[] edge,int[] h) {
		int ret = 0;
		for(int u:edge[v]) {
			if (u == parent) {
				continue;
			}
			int c = dfs(v, u, edge, h);
			if (c >= 0) {
				ret += c + 2;
			}
		}
		if (ret == 0 && h[v] == 0) {
			return -1;
		}
		return ret;
	}
}

Submission Info

Submission Time
Task B - ツリーグラフ
User piroz95
Language Java (OpenJDK 1.7.0)
Score 100
Code Size 1032 Byte
Status AC
Exec Time 513 ms
Memory 24108 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 20
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_line01.txt, subtask1_line02.txt, subtask1_line03.txt, subtask1_line04.txt, subtask1_line05.txt, subtask1_line06.txt, subtask1_random01.txt, subtask1_random02.txt, subtask1_random03.txt, subtask1_random04.txt, subtask1_random05.txt, subtask1_random06.txt, subtask1_random07.txt, subtask1_random08.txt, subtask1_special01.txt, subtask1_special02.txt, subtask1_special03.txt, subtask1_special04.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 479 ms 23304 KB
subtask0_sample_02.txt AC 472 ms 23312 KB
subtask1_line01.txt AC 462 ms 23108 KB
subtask1_line02.txt AC 489 ms 23928 KB
subtask1_line03.txt AC 493 ms 23816 KB
subtask1_line04.txt AC 487 ms 24108 KB
subtask1_line05.txt AC 497 ms 24084 KB
subtask1_line06.txt AC 488 ms 24040 KB
subtask1_random01.txt AC 486 ms 23860 KB
subtask1_random02.txt AC 485 ms 23848 KB
subtask1_random03.txt AC 491 ms 23772 KB
subtask1_random04.txt AC 479 ms 23984 KB
subtask1_random05.txt AC 495 ms 23976 KB
subtask1_random06.txt AC 490 ms 24024 KB
subtask1_random07.txt AC 490 ms 24108 KB
subtask1_random08.txt AC 488 ms 24024 KB
subtask1_special01.txt AC 464 ms 23172 KB
subtask1_special02.txt AC 501 ms 24028 KB
subtask1_special03.txt AC 513 ms 23984 KB
subtask1_special04.txt AC 492 ms 23852 KB