#505416 (C#(csc)) No.1098 LCAs

• 問題: No.1098 LCAs
• ユーザー: Yusei Kato
• 提出日時: 2020-07-02 13:02:19
• 言語: C#(csc) (csc 3.9.0)
• 結果: WA
• 実行時間: -
• コード長: 4,014 bytes
• コンパイル時間: 889 ms
• コンパイル使用メモリ: 68,032 KB
• 実行使用メモリ: 25,632 KB
• 最終ジャッジ日時: 2023-10-13 02:34:55
• 合計ジャッジ時間: 7,889 ms
• ジャッジサーバーID （参考情報）: judge15 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	64 ms; 23,804 KB
testcase_01	AC	65 ms; 23,736 KB
testcase_02	AC	59 ms; 22,700 KB
testcase_03	AC	64 ms; 21,600 KB
testcase_04	AC	65 ms; 23,608 KB
testcase_05	AC	65 ms; 23,624 KB
testcase_06	AC	64 ms; 23,692 KB
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	TLE	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-

ソースコード

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

namespace Problem1098
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = GetInt();
            var raw = new int[N - 1][];
            for(int i = 0; i < N - 1; i++)
            {
                raw[i] = GetIntArray();
            }
            var edge = new List<int>[N];
            for(int i = 0; i < N; i++)
            {
                edge[i] = new List<int>();
            }

            SearchIni(raw, edge);
            var (next, prev, leaves) = BFS(edge);
            Solver(next, prev, leaves);
        }
        public static int GetInt() => int.Parse(Console.ReadLine());
        public static int[] GetIntArray() => Console.ReadLine().Split().Select(int.Parse).ToArray();
        public static void OutLongArray(long[] values)
        {
            foreach (var value in values)
            {
                Console.WriteLine(value);
            }
        }
        public static void Solver (List<int>[] next, int[] prev, List<int> leaves)
        {
            var queue = new Queue<int>();
            for (int i = 0; i < leaves.Count; i++)
            {
                queue.Enqueue(leaves[i]);
            }
            var ans = new long[prev.Length];
            var childsme = new long[prev.Length];
            var sum = new long[prev.Length];
            while(queue.Count != 0)
            {
                var current = queue.Dequeue();
                if(leaves.Contains(current))
                {
                    ans[current] = 1;
                    sum[current] = 1;
                    childsme[current] = 1;
                    if (!queue.Contains(prev[current]) && current != 0)
                    {
                        queue.Enqueue(prev[current]);
                    }
                }
                else
                {
                    childsme[current]++;
                    foreach(var item in next[current])
                    {
                        childsme[current] += childsme[item];
                    }
                    ans[current] = childsme[current] * childsme[current];
                    foreach(var item in next[current])
                    {
                        sum[current] += sum[item];
                    }
                    ans[current] -= sum[current];
                    sum[current] += ans[current];
                    if(current != 0)
                    {
                        queue.Enqueue(prev[current]);
                    }
                }
            }
            OutLongArray(ans);
        }
        public static void SearchIni(int[][] raw, List<int>[] edge)
        {
            for (int i = 0; i < raw.Length; i++)
            {
                edge[raw[i][0] - 1].Add(raw[i][1] - 1);
                edge[raw[i][1] - 1].Add(raw[i][0] - 1);
            }
        }
        public static (List<int>[] next, int[] prev, List<int> leaves) BFS (List<int>[] edge)
        {
            var queue = new Queue<int>();
            var prev = new int[edge.Length];
            var next = new List<int>[edge.Length];
            queue.Enqueue(0);
            var searched = new List<int>();
            var leaves = new List<int>();
            while (queue.Count != 0)
            {
                var current = queue.Dequeue();
                next[current] = new List<int>();
                searched.Add(current);
                bool leaf = true;
                foreach(var item in edge[current])
                {
                    if (!searched.Contains(item))
                    {
                        queue.Enqueue(item);
                        prev[item] = current;
                        next[current].Add(item);
                        leaf = false;
                    }
                }
                if(leaf)
                {
                    leaves.Add(current);
                }
            }
            return (next, prev, leaves);
        }
    }
}