namespace AtCoder; #nullable enable using System.Numerics; static class Extensions { public static T[] Repeat(this int time, Func F) => Enumerable.Range(0, time).Select(_ => F()).ToArray(); } class Graph { public struct Edge { public int Ab { get; set; } public int Ad { get; set; } public T Distance { get; set; } } public int N { get; private init; } public bool Directed { get; private init; } public List> AdjacencyList { get; private init; } public List Edges { get; private init; } public Graph(int verticals, IReadOnlyList edges, bool directed) { N = verticals; Directed = directed; AdjacencyList = new List>(); for (var i = 0; i < N; i++) AdjacencyList.Add(new List<(int, int)>()); Edges = new List(); for (var i = 0; i < edges.Count; i++) { var edge = edges[i]; Edges.Add(edge); AdjacencyList[edge.Ab].Add((edge.Ad, i)); if (!Directed) AdjacencyList[edge.Ad].Add((edge.Ab, i)); } } } class GraphBuilder { public static Graph SimpleGraph(int verticals, (int ab, int ad)[] edges, bool directed) { var e = edges.Select(e => new Graph.Edge { Ab = e.ab, Ad = e.ad, Distance = 1 }).ToList(); return new(verticals, e, directed); } public static Graph Graph(int verticals, (int ab, int ad, T edge)[] edges, bool directed) { var e = edges.Select(e => new Graph.Edge { Ab = e.ab, Ad = e.ad, Distance = e.edge }).ToList(); return new(verticals, e, directed); } } class GraphBase { public required Graph Graph { get; init; } } class Tree : GraphBase { public static Tree? TryConstruct(Graph graph) { if (graph.Directed || graph.Edges.Count + 1 != graph.N) return null; var visited = new bool[graph.N]; int S(int v, int prev) { visited[v] = true; var res = 1; foreach (var (next, _) in graph.AdjacencyList[v]) { if (next == prev || visited[next]) continue; res += S(next, v); } return res; } if (S(0, -1) < graph.N) return null; return new Tree { Graph = graph }; } public interface IRerootingOperator { TResult Identity { get; } TResult Merge(TResult l, TResult r); TResult Finalize(TResult e, int v); } public TResult[] Rerooting(TOperator op = default) where TOperator : struct, IRerootingOperator { var n = Graph.N; var res = new TResult[n]; var adjacencyList = Graph.AdjacencyList; var subTreeValues = new (TResult, int)[n][]; TResult SubTreeValue(int v, int prev) { var merged = op.Identity; var l = adjacencyList[v].Count; subTreeValues[v] = new (TResult, int)[l]; for (var i = 0; i < l; i++) { var (next, index) = adjacencyList[v][i]; if (next == prev) continue; var subTreeValue = SubTreeValue(next, v); subTreeValues[v][i] = (subTreeValue, index); merged = op.Merge(merged, subTreeValue); } return op.Finalize(merged, v); } void Evaluate(int v, int prev, TResult prevValue) { var adjacencies = adjacencyList[v]; var l = adjacencies.Count; for (var i = 0; i < l; i++) if (adjacencies[i].next == prev) { subTreeValues[v][i].Item1 = prevValue; break; } var sumL = new TResult[l]; var sumR = new TResult[l]; sumL[0] = op.Identity; sumR[l - 1] = op.Identity; for (var i = 1; i < l; i++) sumL[i] = op.Merge(sumL[i - 1], subTreeValues[v][i - 1].Item1); for (var i = l - 2; i >= 0; i--) sumR[i] = op.Merge(sumR[i + 1], subTreeValues[v][i + 1].Item1); res[v] = op.Finalize(op.Merge(sumR[0], subTreeValues[v][0].Item1), v); for (var i = 0; i < l; i++) { var next = adjacencies[i].next; if (next == prev) continue; Evaluate(next, v, op.Finalize(op.Merge(sumL[i], sumR[i]), next)); } } SubTreeValue(0, -1); Evaluate(0, -1, op.Identity); return res; } } readonly struct Op : Tree.IRerootingOperator { public long[] Identity => new long[4]; public long[] Finalize(long[] e, int v) { var res = new long[4]; res[0] = 1; for (var i = 1; i <= 3; i++) res[i] += e[i - 1]; return res; } public long[] Merge(long[] l, long[] r) { var y = new long[4]; for (var i = 0; i <= 3; i++) y[i] = l[i] + r[i]; return y; } } class AtCoder { object? Solve() { var n = Int(); var edges = (n - 1).Repeat(() => (Int() - 1, Int() - 1)); var g = GraphBuilder.SimpleGraph(n, edges, false); var t = Tree.TryConstruct(g)!; var s = t.Rerooting(); var ans = 0L; for (var i = 0; i < n; i++) for (var j = 1; j <= 3; j++) ans += s[i][j]; ans /= 2; return ans; } public static void Main() => new AtCoder().Run(); public void Run() { var res = Solve(); if (res != null) { if (res is bool yes) res = yes ? "Yes" : "No"; sw.WriteLine(res); } sw.Flush(); } string[] input = Array.Empty(); int iter = 0; readonly StreamWriter sw = new(Console.OpenStandardOutput()) { AutoFlush = false }; #pragma warning disable IDE0051 string String() { while (iter >= input.Length) (input, iter) = (Console.ReadLine()!.Split(' '), 0); return input[iter++]; } T Input() where T : IParsable => T.Parse(String(), null); int Int() => Input(); void Out(object? x, string? separator = null) { separator ??= Environment.NewLine; if (x is System.Collections.IEnumerable obj and not string) { var firstLine = true; foreach (var item in obj) { if (!firstLine) sw.Write(separator); firstLine = false; sw.Write(item); } } else sw.Write(x); sw.WriteLine(); } #pragma warning restore IDE0051 }