Submission #1302029

---

Source Code Expand

using System;
using System.Collections.Generic;
using System.Linq;
using System.Collections;
using System.Linq.Expressions;

static class Program
{
    static void Main()
    {
        new Magatro().Solve();
    }
}

struct Node
{
    public List<int> Child;
    public int Parent;
}

class T
{
    private Node[] Tree;
    private int Top;
    private List<int>[] R;
    private bool[] HasCry;
    private bool[] H;
    public T(int top, int n, List<int>[] r, bool[] h)
    {
        Tree = new Node[n];
        Top = top;
        R = r;
        HasCry = new bool[n];
        H = h;
    }
    private void MakeTree()
    {
        Queue<int> q = new Queue<int>();
        q.Enqueue(Top);
        Tree[Top].Parent = -1;
        while (q.Count > 0)
        {
            int a = q.Dequeue();
            Tree[a].Child = new List<int>();
            foreach (int i in R[a])
            {
                if (i == Tree[a].Parent)
                {
                    continue;
                }
                Tree[a].Child.Add(i);
                Tree[i].Parent = a;
                q.Enqueue(i);
            }
        }
    }

    private bool HasChild(int num)
    {
        bool flag = false;
        foreach (int i in Tree[num].Child)
        {
            if (HasChild(i))
            {
                flag = true;
            }
        }
        flag |= H[num];
        HasCry[num] = flag;
        return flag;
    }

    private int Cnt(int num)
    {
        int cnt = 0;
        foreach(int i in Tree[num].Child)
        {
            if (HasCry[i])
            {
                cnt += Cnt(i);
                cnt += 2;
            }
        }
        return cnt;
    }

    public int Ans()
    {
        MakeTree();
        HasChild(Top);
        return Cnt(Top);
    }
}

class Magatro
{
    private int N, X;
    private bool[] H;
    private List<int>[] R;

    private void Scan()
    {
        var line = Console.ReadLine().Split(' ');
        N = int.Parse(line[0]);
        X = int.Parse(line[1]);
        H = Console.ReadLine().Split(' ').Select(s => s == "1").ToArray();
        R = new List<int>[N];
        for (int i = 0; i < N; i++)
        {
            R[i] = new List<int>();
        }
        for (int i = 0; i < N - 1; i++)
        {
            line = Console.ReadLine().Split(' ');
            int a = int.Parse(line[0]) - 1;
            int b = int.Parse(line[1]) - 1;
            R[a].Add(b);
            R[b].Add(a);
        }
    }

    public void Solve()
    {
        Scan();
        int ans = int.MaxValue;
        for (int i = 0; i < N; i++)
        {
            var t = new T(i, N, R, H);
            int a = t.Ans();
            ans = Math.Min(ans, a);

        }
        Console.WriteLine(ans);
    }
}

Submission Info

Judge Result