Educational DP Contest V Subtree

問題へのリンク

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

    static long mN;
    static long Hou;

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

    // 木DPとReRootingの設定01 配られてる値が無い時の値
    static long DeriveDefaultNodeVal()
    {
        return 1;
    }

    // 木DPとReRootingの設定02 ノード値を引数として、配る値を返す
    static long DeriveSendVal(long pNodeVal)
    {
        return (1 + pNodeVal) % Hou;
    }

    // 木DPとReRootingの設定03 ノード値と、配られた値を、引数とし、新しいノード値を返す
    static long DeriveNewNodeVal(long pNodeVal, long pSendVal)
    {
        return (pNodeVal * pSendVal) % Hou;
    }

    // 木DPとReRootingの設定04 配る値のListを引数として、最終的な配る値を返す
    static long DeriveMergedSendVal(List<long> pSendValList)
    {
        long SendVal = DeriveDefaultNodeVal();
        foreach (long EachSendVal in pSendValList) {
            SendVal = DeriveNewNodeVal(SendVal, EachSendVal);
        }
        return SendVal;
    }

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

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

        SplitAct(InputList[0]);
        mN = wkArr[0];
        Hou = wkArr[1];

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            long S = wkArr[0];
            long T = wkArr[1];

            if (mToNodeListDict.ContainsKey(S) == false) {
                mToNodeListDict[S] = new List<long>();
            }
            if (mToNodeListDict.ContainsKey(T) == false) {
                mToNodeListDict[T] = new List<long>();
            }
            mToNodeListDict[S].Add(T);
            mToNodeListDict[T].Add(S);
        }

        // 前後に累積Prodを使うので、ノード番号の昇順にソート
        foreach (var EachPair in mToNodeListDict) {
            EachPair.Value.Sort();
        }

        // 黒で塗る場合の数[ノード]なDP表
        var TreeDPDict = new Dictionary<long, long>();

        // 根から葉に向かってDFSしてノードのListを返す
        List<JyoutaiDef1> DFSResult = ExecDFS1(1);
        DFSResult.Reverse(); // 葉から根への順番にする

        foreach (JyoutaiDef1 EachJyoutai in DFSResult) {
            // 親ノードに配る木DP
            int Node = EachJyoutai.CurrNode;
            if (TreeDPDict.ContainsKey(Node) == false) {
                TreeDPDict[Node] = DeriveDefaultNodeVal();
            }

            int ParentNode = EachJyoutai.ParentNode;

            // 根ノードの場合
            if (ParentNode == -1) continue;

            if (TreeDPDict.ContainsKey(ParentNode) == false) {
                TreeDPDict[ParentNode] = DeriveDefaultNodeVal();
            }
            TreeDPDict[ParentNode] =
                DeriveNewNodeVal(TreeDPDict[ParentNode], DeriveSendVal(TreeDPDict[Node]));
        }

        // 木DPの結果
        //foreach (var EachPair in TreeDPDict.OrderBy(pX => pX.Key)) {
        //    Console.WriteLine("TreeDPDict[{0}]={1}", EachPair.Key, EachPair.Value);
        //}

        // ReRootingなDFSを行う
        var sb = new System.Text.StringBuilder();
        foreach (long EachLong in ExecDFS2(1, TreeDPDict)) {
            sb.AppendLine(EachLong.ToString());
        }
        Console.Write(sb.ToString());
    }

    // 根から葉に向かってDFSしてノードのListを返す
    struct JyoutaiDef1
    {
        internal int CurrNode;
        internal int ParentNode;
    }
    static List<JyoutaiDef1> ExecDFS1(int pRootNode)
    {
        var WillReturn = new List<JyoutaiDef1>();

        var Stk = new Stack<JyoutaiDef1>();
        JyoutaiDef1 WillPush;
        WillPush.CurrNode = pRootNode;
        WillPush.ParentNode = -1;
        Stk.Push(WillPush);

        var VisitedSet = new HashSet<int>();
        VisitedSet.Add(pRootNode);

        while (Stk.Count > 0) {
            JyoutaiDef1 Popped = Stk.Pop();
            WillReturn.Add(Popped);
            if (mToNodeListDict.ContainsKey(Popped.CurrNode) == false) {
                continue;
            }
            foreach (int EachToNode in mToNodeListDict[Popped.CurrNode]) {
                if (VisitedSet.Add(EachToNode)) {
                    WillPush.CurrNode = EachToNode;
                    WillPush.ParentNode = Popped.CurrNode;
                    Stk.Push(WillPush);
                }
            }
        }
        return WillReturn;
    }

    // ReRootingなDFSを行う
    struct JyoutaiDef2
    {
        internal long PrevRootNode;
        internal long PrevRootVal;
        internal long CurrRootNode;
        internal long CurrRootVal;
    }
    static IEnumerable<long> ExecDFS2(long pRootNode, Dictionary<long, long> pTreeDPDict)
    {
        var WillReturn = new List<long>();

        var Stk = new Stack<JyoutaiDef2>();
        JyoutaiDef2 WillPush;
        WillPush.PrevRootNode = -1;
        WillPush.PrevRootVal = -1;
        WillPush.CurrRootNode = pRootNode;
        WillPush.CurrRootVal = pTreeDPDict[pRootNode];
        Stk.Push(WillPush);

        var VisitedSet = new HashSet<long>();
        VisitedSet.Add(pRootNode);

        var AnswerDict = new Dictionary<long, long>();
        while (Stk.Count > 0) {
            JyoutaiDef2 Popped = Stk.Pop();
            AnswerDict[Popped.CurrRootNode] = Popped.CurrRootVal;

            // 累積Prodを管理する
            int ChildCnt = 0;
            if (mToNodeListDict.ContainsKey(Popped.CurrRootNode)) {
                mToNodeListDict[Popped.CurrRootNode].Remove(Popped.PrevRootNode);
                ChildCnt = mToNodeListDict[Popped.CurrRootNode].Count;
            }
            if (ChildCnt == 0) continue;

            long[] RunProdSei = new long[ChildCnt]; // 正方向の累積Prod
            long[] RunProdRev = new long[ChildCnt]; // 逆方向の累積Prod

            long StaNode = mToNodeListDict[Popped.CurrRootNode][0];
            long EndNode = mToNodeListDict[Popped.CurrRootNode][ChildCnt - 1];
            RunProdSei[0] = DeriveSendVal(pTreeDPDict[StaNode]);
            RunProdRev[RunProdRev.GetUpperBound(0)] = DeriveSendVal(pTreeDPDict[EndNode]);

            for (int I = 1; I <= ChildCnt - 1; I++) {
                long CurrChildNode = mToNodeListDict[Popped.CurrRootNode][I];
                RunProdSei[I] =
                    DeriveNewNodeVal(RunProdSei[I - 1], DeriveSendVal(pTreeDPDict[CurrChildNode]));
            }
            for (int I = ChildCnt - 2; 0 <= I; I--) {
                long CurrChildNode = mToNodeListDict[Popped.CurrRootNode][I];
                RunProdRev[I] =
                    DeriveNewNodeVal(RunProdRev[I + 1], DeriveSendVal(pTreeDPDict[CurrChildNode]));
            }

            // 状態の遷移
            for (int I = 0; I <= mToNodeListDict[Popped.CurrRootNode].Count - 1; I++) {
                long CurrRootNode = mToNodeListDict[Popped.CurrRootNode][I];
                if (VisitedSet.Add(CurrRootNode) == false) {
                    continue;
                }

                // 左方向の累積Prod
                long LeftRunProd = DeriveDefaultNodeVal();
                bool HasLeftRunVal = false;
                if (I > 0) {
                    LeftRunProd = RunProdSei[I - 1];
                    HasLeftRunVal = true;
                }

                // 右方向の累積Prod
                long RightRunProd = DeriveDefaultNodeVal();
                bool HasRightRunVal = false;
                if (I < mToNodeListDict[Popped.CurrRootNode].Count - 1) {
                    RightRunProd = RunProdRev[I + 1];
                    HasRightRunVal = true;
                }

                WillPush.PrevRootNode = Popped.CurrRootNode;
                var PrevRootValKouhoList = new List<long>();
                if (HasLeftRunVal) PrevRootValKouhoList.Add(LeftRunProd);
                if (HasRightRunVal) PrevRootValKouhoList.Add(RightRunProd);
                if (Popped.PrevRootNode > -1) {
                    PrevRootValKouhoList.Add(DeriveSendVal(Popped.PrevRootVal));
                }
                WillPush.PrevRootVal = DeriveMergedSendVal(PrevRootValKouhoList);

                WillPush.CurrRootNode = CurrRootNode;
                var CurrRootValKouhoList = new List<long>();
                CurrRootValKouhoList.Add(pTreeDPDict[CurrRootNode]);
                CurrRootValKouhoList.Add(DeriveSendVal(WillPush.PrevRootVal));
                WillPush.CurrRootVal = DeriveMergedSendVal(CurrRootValKouhoList);

                Stk.Push(WillPush);
            }
        }

        foreach (var EachPair in AnswerDict.OrderBy(pX => pX.Key)) {
            yield return EachPair.Value;
        }
    }
}

解説

根ノードが必ず黒なことをふまえつつ

ノードごとに
このノードを黒く塗った時の、部分木の場合の数をX
このノードを白く塗った時の、部分木の場合の数をY
として考えると

葉ノードは、(X,Y) = (1,1) と分かります。
1つ上のノードは、
X = (子ノード達の(X+Y)の総積)
Y = 1
と分かります。

以上により、木DPとReRootingで解くことができます。