using System; using System.Collections.Generic; using System.IO; using System.Linq; using System.Text; using System.Runtime.CompilerServices; using System.Runtime.InteropServices; using YukicoderContest255.Extensions; using YukicoderContest255.Questions; namespace YukicoderContest255.Questions { public class QuestionC : AtCoderQuestionBase { BasicGraph tree; public override IEnumerable Solve(TextReader inputStream) { var nodes = inputStream.ReadInt(); tree = new BasicGraph(nodes); var isRoot = Enumerable.Repeat(true, nodes).ToArray(); for (int i = 0; i < nodes - 1; i++) { var (a, b) = inputStream.ReadValue(); a--; b--; tree.AddEdge(new BasicEdge(a, b)); isRoot[b] = false; } var root = -1; for (int i = 0; i < isRoot.Length; i++) { if (isRoot[i]) { root = i; break; } } yield return Dfs(root, 0, 0) % 1000000007; } long Dfs(int node, int parents, long sum) { sum += parents; long childrenSum = 0; foreach (var edge in tree[node]) { childrenSum += Dfs(edge.To.Index, parents + 1, sum); } return sum + childrenSum; } public interface INode { public int Index { get; } } public interface IEdge where TNode : INode { TNode From { get; } TNode To { get; } } public interface IWeightedEdge : IEdge where TNode : INode { long Weight { get; } } public interface IGraph where TEdge : IEdge where TNode : INode { IEnumerable this[TNode node] { get; } IEnumerable Edges { get; } IEnumerable Nodes { get; } int NodeCount { get; } } public interface IWeightedGraph : IGraph where TEdge : IWeightedEdge where TNode : INode { } [StructLayout(LayoutKind.Auto)] public readonly struct BasicNode : INode, IEquatable { public int Index { get; } public BasicNode(int index) { Index = index; } public override string ToString() => Index.ToString(); public override bool Equals(object obj) => obj is BasicNode node && Equals(node); public bool Equals(BasicNode other) => Index == other.Index; public override int GetHashCode() => HashCode.Combine(Index); public static bool operator ==(BasicNode left, BasicNode right) => left.Equals(right); public static bool operator !=(BasicNode left, BasicNode right) => !(left == right); public static implicit operator BasicNode(int value) => new BasicNode(value); } [StructLayout(LayoutKind.Auto)] public readonly struct BasicEdge : IEdge { public BasicNode From { get; } public BasicNode To { get; } public BasicEdge(int from, int to) { From = from; To = to; } public override string ToString() => $"{From}-->{To}"; } [StructLayout(LayoutKind.Auto)] public readonly struct WeightedEdge : IWeightedEdge { public BasicNode From { get; } public BasicNode To { get; } public long Weight { get; } public WeightedEdge(int from, int to) : this(from, to, 1) { } public WeightedEdge(int from, int to, long weight) { From = from; To = to; Weight = weight; } public override string ToString() => $"{From}--[{Weight}]-->{To}"; } public class BasicGraph : IGraph { private readonly List[] _edges; public IEnumerable this[BasicNode node] => _edges[node.Index]; public IEnumerable Edges => Nodes.SelectMany(node => this[node]); public IEnumerable Nodes => Enumerable.Range(0, NodeCount).Select(i => new BasicNode(i)); public int NodeCount { get; } public BasicGraph(int nodeCount) : this(nodeCount, Enumerable.Empty()) { } public BasicGraph(int nodeCount, IEnumerable edges) { _edges = Enumerable.Repeat(0, nodeCount).Select(_ => new List()).ToArray(); NodeCount = nodeCount; foreach (var edge in edges) { AddEdge(edge); } } public BasicGraph(int nodeCount, IEnumerable> distances) { _edges = new List[nodeCount]; int i = 0; foreach (var row in distances) { _edges[i] = new List(nodeCount); int j = 0; foreach (var distance in row) { if (distance == 1) { _edges[i].Add(new BasicEdge(i, j++)); } } i++; } } public void AddEdge(BasicEdge edge) => _edges[edge.From.Index].Add(edge); } } } namespace YukicoderContest255 { class Program { static void Main(string[] args) { IAtCoderQuestion question = new QuestionC(); var answers = question.Solve(Console.In); var writer = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; Console.SetOut(writer); foreach (var answer in answers) { Console.WriteLine(answer); } Console.Out.Flush(); } } } #region Base Class namespace YukicoderContest255.Questions { public interface IAtCoderQuestion { IEnumerable Solve(string input); IEnumerable Solve(TextReader inputStream); } public abstract class AtCoderQuestionBase : IAtCoderQuestion { public IEnumerable Solve(string input) { var stream = new MemoryStream(Encoding.Unicode.GetBytes(input)); var reader = new StreamReader(stream, Encoding.Unicode); return Solve(reader); } public abstract IEnumerable Solve(TextReader inputStream); } } #endregion #region Extensions namespace YukicoderContest255.Extensions { public static class TextReaderExtensions { public static int ReadInt(this TextReader reader) => int.Parse(ReadString(reader)); public static long ReadLong(this TextReader reader) => long.Parse(ReadString(reader)); public static double ReadDouble(this TextReader reader) => double.Parse(ReadString(reader)); public static string ReadString(this TextReader reader) => reader.ReadLine(); public static int[] ReadIntArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(int.Parse).ToArray(); public static long[] ReadLongArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(long.Parse).ToArray(); public static double[] ReadDoubleArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(double.Parse).ToArray(); public static string[] ReadStringArray(this TextReader reader, char separator = ' ') => reader.ReadLine().Split(separator); // Supports primitive type only. public static T1 ReadValue(this TextReader reader) => (T1)Convert.ChangeType(reader.ReadLine(), typeof(T1)); public static (T1, T2) ReadValue(this TextReader reader, char separator = ' ') { var inputs = ReadStringArray(reader, separator); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); return (v1, v2); } public static (T1, T2, T3) ReadValue(this TextReader reader, char separator = ' ') { var inputs = ReadStringArray(reader, separator); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3)); return (v1, v2, v3); } public static (T1, T2, T3, T4) ReadValue(this TextReader reader, char separator = ' ') { var inputs = ReadStringArray(reader, separator); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3)); var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4)); return (v1, v2, v3, v4); } public static (T1, T2, T3, T4, T5) ReadValue(this TextReader reader, char separator = ' ') { var inputs = ReadStringArray(reader, separator); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3)); var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4)); var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5)); return (v1, v2, v3, v4, v5); } public static (T1, T2, T3, T4, T5, T6) ReadValue(this TextReader reader, char separator = ' ') { var inputs = ReadStringArray(reader, separator); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3)); var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4)); var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5)); var v6 = (T6)Convert.ChangeType(inputs[5], typeof(T6)); return (v1, v2, v3, v4, v5, v6); } public static (T1, T2, T3, T4, T5, T6, T7) ReadValue(this TextReader reader, char separator = ' ') { var inputs = ReadStringArray(reader, separator); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3)); var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4)); var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5)); var v6 = (T6)Convert.ChangeType(inputs[5], typeof(T6)); var v7 = (T7)Convert.ChangeType(inputs[6], typeof(T7)); return (v1, v2, v3, v4, v5, v6, v7); } public static (T1, T2, T3, T4, T5, T6, T7, T8) ReadValue(this TextReader reader, char separator = ' ') { var inputs = ReadStringArray(reader, separator); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3)); var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4)); var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5)); var v6 = (T6)Convert.ChangeType(inputs[5], typeof(T6)); var v7 = (T7)Convert.ChangeType(inputs[6], typeof(T7)); var v8 = (T8)Convert.ChangeType(inputs[7], typeof(T8)); return (v1, v2, v3, v4, v5, v6, v7, v8); } } } #endregion