結果

問題 No.1098 LCAs
コンテスト
ユーザー Yusei Kato
提出日時 2020-07-02 13:02:19
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 4,014 bytes
コンパイル時間 923 ms
コンパイル使用メモリ 107,520 KB
実行使用メモリ 62,064 KB
最終ジャッジ日時 2024-09-15 00:18:26
合計ジャッジ時間 6,728 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 4 WA * 11 TLE * 1 -- * 12
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

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);
        }
    }
}
0