Even Tree - study the code -

EvenTreeStudy4.cs

using System;
using System.Collections.Generic;
using System.Text;

public class Node
{
    private int id;
    private List<Node> children = new List<Node>();
    private bool dirty = false;
    private int subtreeSize = 1;

    public Node(int id)
    {
        this.id = id;
    }

    public void RemoveChild(int id)
    {
        for (int i = 0; i < this.children.Count; i++)
        {
            if (this.children[i].id == id)
            {
                this.children.RemoveAt(i);
                break;
            }
        }
        this.dirty = true;
    }

    public void AddChild(Node c)
    {
        this.children.Add(c);
        this.dirty = true;
    }

    public IEnumerable<Node> Children { get { return this.children; } }

    public int Id { get { return this.id; } }

    public int SubtreeSize
    {
        get
        {
            if (this.dirty)
            {
                int count = 0;
                Stack<Node> stack = new Stack<Node>();
                stack.Push(this);
                while (stack.Count > 0)
                {
                    Node n = stack.Pop();
                    count++;
                    foreach (Node c in n.children)
                    {
                        stack.Push(c);
                    }
                }
                this.subtreeSize = count;
                this.dirty = false;
            }

            return this.subtreeSize;
        }
    }
}

public class Solution
{
    public static IEnumerable<string> Solve(string[] input)
    {
        int N = 0;
        List<int[]> edges = new List<int[]>();
        for (int i = 0; i < input.Length; i++)
        {
            string[] s = input[i].Split(' ');
            int[] e = new int[2];
            e[0] = int.Parse(s[0]);
            e[1] = int.Parse(s[1]);
            if (i == 0)
            {
                N = e[0];
            }
            else
            {
                e[0]--;
                e[1]--;
                edges.Add(e);
            }
        }

        Node[] nodes = new Node[N];
        for (int i = 0; i < nodes.Length; i++)
        {
            nodes[i] = new Node(i);
        }
        foreach (int[] e in edges)
        {
            nodes[e[1]].AddChild(nodes[e[0]]);
        }

        int count = 0;
        Stack<Node> stack = new Stack<Node>();
        stack.Push(nodes[0]);
        while (stack.Count > 0)
        {
            Node n = stack.Pop();
            foreach (Node c in n.Children)
            {
                if (c.SubtreeSize % 2 == 0)
                {
                    count++;
                }
                stack.Push(c);
            }
        }

        return new String[] { count + "" };
    }
    
    public static void Main(string[] args)
    {
        String[] input = Console.In.ReadToEnd().Split(new char[]{ '\n' }, StringSplitOptions.RemoveEmptyEntries);
        foreach (String s in Solve(input))
        {
            Console.Out.WriteLine(s);
        }
    }
}