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[N]; for(int i = 0; i < N; i++) { edge[i] = new List(); } 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[] next, int[] prev, List leaves) { var queue = new Queue(); 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[] 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[] next, int[] prev, List leaves) BFS (List[] edge) { var queue = new Queue(); var prev = new int[edge.Length]; var next = new List[edge.Length]; queue.Enqueue(0); var searched = new List(); var leaves = new List(); while (queue.Count != 0) { var current = queue.Dequeue(); next[current] = new List(); 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); } } }