Submission #287617


Source Code Expand

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;

class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }

    int n, x;
    int[] h;

    List<int>[] es;

    void calc()
    {
        Scanner cin = new Scanner();
        n = cin.nextInt();
        x = cin.nextInt() - 1;
        h = new int[n];
        for (int i = 0; i < n; i++)
        {
            h[i] = cin.nextInt();
        }

        es = new List<int>[n];
        for (int i = 0; i < n; i++)
        {
            es[i] = new List<int>();
        }

        for (int i = 0; i < n-1; i++)
        {
            int a = cin.nextInt() - 1;
            int b = cin.nextInt() - 1;
            es[a].Add(b);
            es[b].Add(a);
        }
        int ret = dfs(x, -1) - 2;
        if (ret < 0) ret = 0;
        Console.WriteLine(ret);
    }

    int dfs(int now, int pre)
    {
        int ret = 0;
        foreach (var next in es[now])
        {
            if (pre == next) continue;
            ret += dfs(next, now);
        }
        if (ret == 0 && h[now] == 0) return 0;
        ret += 2;
        return ret;
    }

    


}




class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        do
        {
            s = Console.ReadLine().Split(cs, StringSplitOptions.RemoveEmptyEntries);
        } while ((s.Length == 1 && s[0] == "") || s.Length == 0);
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }

}

Submission Info

Submission Time
Task B - ツリーグラフ
User chokudai
Language C# (Mono 2.10.8.1)
Score 100
Code Size 2008 Byte
Status AC
Exec Time 146 ms
Memory 7944 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 140 ms 7896 KB
subtask0_sample_02.txt AC 135 ms 7820 KB
subtask1_line01.txt AC 137 ms 7820 KB
subtask1_line02.txt AC 137 ms 7852 KB
subtask1_line03.txt AC 136 ms 7848 KB
subtask1_line04.txt AC 137 ms 7824 KB
subtask1_line05.txt AC 138 ms 7776 KB
subtask1_line06.txt AC 136 ms 7772 KB
subtask1_random01.txt AC 140 ms 7944 KB
subtask1_random02.txt AC 135 ms 7832 KB
subtask1_random03.txt AC 135 ms 7832 KB
subtask1_random04.txt AC 138 ms 7840 KB
subtask1_random05.txt AC 135 ms 7820 KB
subtask1_random06.txt AC 138 ms 7832 KB
subtask1_random07.txt AC 135 ms 7848 KB
subtask1_random08.txt AC 137 ms 7852 KB
subtask1_special01.txt AC 133 ms 7836 KB
subtask1_special02.txt AC 136 ms 7820 KB
subtask1_special03.txt AC 146 ms 7852 KB
subtask1_special04.txt AC 139 ms 7844 KB