ABC026-C 高橋君の給料

問題へのリンク

C#のソース

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

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("5");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("7");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("2");
            WillReturn.Add("2");
            WillReturn.Add("3");
            WillReturn.Add("3");
            //7
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("6");
            WillReturn.Add("1");
            WillReturn.Add("2");
            WillReturn.Add("3");
            WillReturn.Add("3");
            WillReturn.Add("2");
            //11
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("10");
            WillReturn.Add("1");
            WillReturn.Add("2");
            WillReturn.Add("3");
            WillReturn.Add("4");
            WillReturn.Add("5");
            WillReturn.Add("6");
            WillReturn.Add("7");
            WillReturn.Add("8");
            WillReturn.Add("9");
            //1023
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    // 隣接リスト
    static Dictionary<int, List<int>> mToNodeArrDict = new Dictionary<int, List<int>>();

    static Dictionary<int, int> mDPDict = new Dictionary<int, int>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        int N = int.Parse(InputList[0]);

        for (int I = 1; I <= N - 1; I++) {
            int ParentNode = int.Parse(InputList[I]);
            int ChildNode = I + 1;

            if (mToNodeArrDict.ContainsKey(ParentNode) == false) {
                mToNodeArrDict[ParentNode] = new List<int>();
            }
            mToNodeArrDict[ParentNode].Add(ChildNode);
        }

        // メモ化再帰で解く
        DFS(1);

        Console.WriteLine(mDPDict[1]);
    }

    static int DFS(int pCurrNode)
    {
        if (mDPDict.ContainsKey(pCurrNode)) {
            return mDPDict[pCurrNode];
        }
        var ChildNodeList = new List<int>();
        if (mToNodeArrDict.ContainsKey(pCurrNode)) {
            ChildNodeList.AddRange(mToNodeArrDict[pCurrNode]);
        }

        var KouhoList = new List<int>();
        ChildNodeList.ForEach(pX => KouhoList.Add(DFS(pX)));

        int CurrVal = 1;
        if (KouhoList.Count > 0) {
            CurrVal += KouhoList.Min();
            CurrVal += KouhoList.Max();
        }
        return mDPDict[pCurrNode] = CurrVal;
    }
}

解説

メモ化再帰で解いてます。