ABC036-D 塗り絵

問題へのリンク

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("2 5");
            WillReturn.Add("1 5");
            WillReturn.Add("2 4");
            WillReturn.Add("3 2");
            //14
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10");
            WillReturn.Add("7 9");
            WillReturn.Add("8 1");
            WillReturn.Add("9 6");
            WillReturn.Add("10 8");
            WillReturn.Add("8 6");
            WillReturn.Add("10 3");
            WillReturn.Add("5 8");
            WillReturn.Add("4 8");
            WillReturn.Add("2 5");
            //192
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static Dictionary<int, List<int>> mToNodeListDict = new Dictionary<int, List<int>>();

    const long Hou = 1000000007;

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();

        long N = long.Parse(InputList[0]);
        long UB = N;

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            int A = wkArr[0];
            int B = wkArr[1];

            if (mToNodeListDict.ContainsKey(A) == false) {
                mToNodeListDict[A] = new List<int>();
            }
            if (mToNodeListDict.ContainsKey(B) == false) {
                mToNodeListDict[B] = new List<int>();
            }
            mToNodeListDict[A].Add(B);
            mToNodeListDict[B].Add(A);
        }

        List<JyoutaiDef> OrderedNodeList = ExecDFS();

        // 場合の数[ノード,白色か？]
        long[,] DPArr = new long[UB + 1, 2];

        // 登場したノードのSet
        var AppearedNodeSet = new HashSet<int>();

        for (int I = OrderedNodeList.Count - 1; 0 <= I; I--) {
            AppearedNodeSet.Add(OrderedNodeList[I].CurrNode);

            // 葉ノードかの判定
            bool IsLeaf = false;
            if (I == OrderedNodeList.Count - 1
             || OrderedNodeList[I].Level >= OrderedNodeList[I + 1].Level) {
                IsLeaf = true;
            }

            if (IsLeaf) {
                DPArr[OrderedNodeList[I].CurrNode, 0] = 1;
                DPArr[OrderedNodeList[I].CurrNode, 1] = 1;
            }
            else {
                long BlackCnt = 1;
                long WhiteCnt = 1;
                // 子ノードごとに、部分木の塗り分けの違いは、区別されるので、積の法則を使う
                foreach (int EachChildNode in mToNodeListDict[OrderedNodeList[I].CurrNode]) {
                    if (AppearedNodeSet.Contains(EachChildNode) == false) {
                        continue;
                    }
                    long wkBlackCnt = DPArr[EachChildNode, 1];
                    long wkWhiteCnt = DPArr[EachChildNode, 0] + DPArr[EachChildNode, 1];
                    wkWhiteCnt %= Hou;
                    BlackCnt *= wkBlackCnt; BlackCnt %= Hou;
                    WhiteCnt *= wkWhiteCnt; WhiteCnt %= Hou;
                }
                DPArr[OrderedNodeList[I].CurrNode, 0] = BlackCnt;
                DPArr[OrderedNodeList[I].CurrNode, 1] = WhiteCnt;
            }
        }
        long Answer = 0;
        Answer += DPArr[1, 0]; Answer %= Hou;
        Answer += DPArr[1, 1]; Answer %= Hou;
        Console.WriteLine(Answer);
    }

    struct JyoutaiDef
    {
        internal int CurrNode;
        internal int PrevNode;
        internal int Level;
    }

    // DFSを行い、訪問順序でノードを返す
    static List<JyoutaiDef> ExecDFS()
    {
        var WillReturn = new List<JyoutaiDef>();

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrNode = 1;
        WillPush.PrevNode = -1;
        WillPush.Level = 1;
        Stk.Push(WillPush);

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            WillReturn.Add(Popped);

            if (mToNodeListDict.ContainsKey(Popped.CurrNode)) {
                foreach (int EachToNode in mToNodeListDict[Popped.CurrNode]) {
                    if (EachToNode == Popped.PrevNode) continue;

                    WillPush.CurrNode = EachToNode;
                    WillPush.PrevNode = Popped.CurrNode;
                    WillPush.Level = Popped.Level + 1;
                    Stk.Push(WillPush);
                }
            }
        }
        return WillReturn;
    }
}

解説

手順01 根付き木とみなして、DFSの訪問順でノードをソートします。
手順02 葉ノードであれば、白と黒の両方がそれぞれ1通りです。
手順03 葉ノードでない場合、
       白に塗るのであれば、白に塗れる子ノードの場合の数の、積の法則での積が、場合の数になります
       黒に塗るのであれば、黒に塗れる子ノードの場合の数の、積の法則での積が、場合の数になります

以上の手順で、根ノードの場合の数が解になります。

類題

Educational DP Contest P Independent Set