ABC187-E Through Path

問題へのリンク

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 2");
            WillReturn.Add("2 3");
            WillReturn.Add("2 4");
            WillReturn.Add("4 5");
            WillReturn.Add("4");
            WillReturn.Add("1 1 1");
            WillReturn.Add("1 4 10");
            WillReturn.Add("2 1 100");
            WillReturn.Add("2 2 1000");
            //11
            //110
            //1110
            //110
            //100
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("7");
            WillReturn.Add("2 1");
            WillReturn.Add("2 3");
            WillReturn.Add("4 2");
            WillReturn.Add("4 5");
            WillReturn.Add("6 1");
            WillReturn.Add("3 7");
            WillReturn.Add("7");
            WillReturn.Add("2 2 1");
            WillReturn.Add("1 3 2");
            WillReturn.Add("2 2 4");
            WillReturn.Add("1 6 8");
            WillReturn.Add("1 3 16");
            WillReturn.Add("2 4 32");
            WillReturn.Add("2 1 64");
            //72
            //8
            //13
            //26
            //58
            //72
            //5
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("11");
            WillReturn.Add("2 1");
            WillReturn.Add("1 3");
            WillReturn.Add("3 4");
            WillReturn.Add("5 2");
            WillReturn.Add("1 6");
            WillReturn.Add("1 7");
            WillReturn.Add("5 8");
            WillReturn.Add("3 9");
            WillReturn.Add("3 10");
            WillReturn.Add("11 4");
            WillReturn.Add("10");
            WillReturn.Add("2 6 688");
            WillReturn.Add("1 10 856");
            WillReturn.Add("1 8 680");
            WillReturn.Add("1 8 182");
            WillReturn.Add("2 2 452");
            WillReturn.Add("2 4 183");
            WillReturn.Add("2 6 518");
            WillReturn.Add("1 3 612");
            WillReturn.Add("2 6 339");
            WillReturn.Add("2 3 206");
            //1657
            //1657
            //2109
            //1703
            //1474
            //1657
            //3202
            //1474
            //1247
            //2109
            //2559
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mN;

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

    // 枝の情報
    struct EdgeIndoDef
    {
        internal long A;
        internal long B;
    }
    static Dictionary<long, EdgeIndoDef> mEdgeIndoDict = new Dictionary<long, EdgeIndoDef>();

    // クエリ情報
    struct QueryDef
    {
        internal long T;
        internal long E;
        internal long X;
    }
    static List<QueryDef> mQueryList = new List<QueryDef>();

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

        mN = long.Parse(InputList[0]);

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

        long I = 1;
        foreach (string EachStr in InputList.Skip(1).Take((int)mN - 1)) {
            SplitAct(EachStr);
            long FromNode = wkArr[0];
            long ToNode = wkArr[1];

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

            mEdgeIndoDict[I++] = new EdgeIndoDef() { A = FromNode, B = ToNode };
        }

        foreach (string EachStr in InputList.Skip((int)mN + 1)) {
            SplitAct(EachStr);
            QueryDef WillAdd;
            WillAdd.T = wkArr[0];
            WillAdd.E = wkArr[1];
            WillAdd.X = wkArr[2];
            mQueryList.Add(WillAdd);
        }
        Solve();
    }

    class NodeInfoDef
    {
        internal long Level;
        internal long SumX;
    }
    static Dictionary<long, NodeInfoDef> mNodeInfoDict = new Dictionary<long, NodeInfoDef>();

    static long mAllSum = 0; // 全ノードへの加算用

    static void Solve()
    {
        // BFSでレベルを設定する
        ExecBFS1();

        // クエリの処理
        foreach (QueryDef EachQuery in mQueryList) {
            long T = EachQuery.T;
            long E = EachQuery.E;
            long X = EachQuery.X;

            long StaNode = mEdgeIndoDict[E].A;
            long NGNode = mEdgeIndoDict[E].B;

            if (T == 2) {
                StaNode = mEdgeIndoDict[E].B;
                NGNode = mEdgeIndoDict[E].A;
            }

            // 開始ノードが根側で、NGノードが葉側の場合
            if (mNodeInfoDict[StaNode].Level < mNodeInfoDict[NGNode].Level) {
                mAllSum += X;
                mNodeInfoDict[NGNode].SumX -= X;
            }

            // 開始ノードが葉側で、NGノードが根側の場合
            if (mNodeInfoDict[StaNode].Level > mNodeInfoDict[NGNode].Level) {
                mNodeInfoDict[StaNode].SumX += X;
            }
        }

        // BFSで累積和を求める
        List<JyoutaiDef2> Jyoutai2List = ExecBFS2();
        Jyoutai2List = Jyoutai2List.OrderBy(pX => pX.CurrNode).ToList();
        Jyoutai2List.ForEach(pX => Console.WriteLine(pX.RunSumX));
    }

    // BFSでレベルを設定する
    struct JyoutaiDef1
    {
        internal long CurrNode;
        internal long Level;
    }
    static void ExecBFS1()
    {
        var Que = new Queue<JyoutaiDef1>();
        JyoutaiDef1 WillEnqueue;
        WillEnqueue.CurrNode = 1;
        WillEnqueue.Level = 1;
        Que.Enqueue(WillEnqueue);

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

        while (Que.Count > 0) {
            JyoutaiDef1 Dequeued = Que.Dequeue();

            mNodeInfoDict[Dequeued.CurrNode] = new NodeInfoDef();
            mNodeInfoDict[Dequeued.CurrNode].Level = Dequeued.Level;
            mNodeInfoDict[Dequeued.CurrNode].SumX = 0;

            foreach (long EachToNode in mToNodeListDict[Dequeued.CurrNode]) {
                if (VisitedSet.Add(EachToNode)) {
                    WillEnqueue.CurrNode = EachToNode;
                    WillEnqueue.Level = Dequeued.Level + 1;
                    Que.Enqueue(WillEnqueue);
                }
            }
        }
    }

    // BFSで累積和を求める
    struct JyoutaiDef2
    {
        internal long CurrNode;
        internal long RunSumX;
    }
    static List<JyoutaiDef2> ExecBFS2()
    {
        var WillReturn = new List<JyoutaiDef2>();

        var Que = new Queue<JyoutaiDef2>();
        JyoutaiDef2 WillEnqueue;
        WillEnqueue.CurrNode = 1;
        WillEnqueue.RunSumX = mNodeInfoDict[1].SumX + mAllSum;
        Que.Enqueue(WillEnqueue);

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

        while (Que.Count > 0) {
            JyoutaiDef2 Dequeued = Que.Dequeue();
            WillReturn.Add(Dequeued);

            foreach (long EachToNode in mToNodeListDict[Dequeued.CurrNode]) {
                if (VisitedSet.Add(EachToNode)) {
                    WillEnqueue.CurrNode = EachToNode;
                    WillEnqueue.RunSumX = Dequeued.RunSumX + mNodeInfoDict[EachToNode].SumX;
                    Que.Enqueue(WillEnqueue);
                }
            }
        }
        return WillReturn;
    }
}

解説

まず、根付き木として、各ノードにレベルを振ります。

次に、各クエリで、2つのノードが根側にあるか葉側にあるかは
レベルの大小で判定できるので、
葉側に足す場合は、葉側のノードに加算。
根側に足す場合は、全ノードに加算してから、葉ノードにマイナスを掛けた値を加算。
としてます。

最後に、根ノードからBFSで累積和を求めれば、解になります。