Sum of Simple Path Lengths in a Directed Tree

Given a tree with n nodes, each undirected edge is assigned a fixed direction, resulting in a directed acyclic graph. A simple path in a directed graph is defined as a sequence of distinct vertices a₁ → a₂ → a₃ → ... → a_x where the length of the path is the number of edges in it. Your task is to compute the sum of the lengths of all simple paths in the directed tree.

Note: Each edge in the tree appears exactly once in the input as a directed edge from u to v.

The answer can be formulated in terms of DP. Denote by \(dp_{cnt}(u)\) the number of simple paths starting at vertex \(u\) and by \(dp_{sum}(u)\) the sum of lengths of simple paths starting at vertex \(u\). Then, for each vertex \(u\) we have:

[ \begin{aligned} dp_{cnt}(u) &= \sum_{v \in out[u]} \Big(1 + dp_{cnt}(v)\Big), \ dp_{sum}(u) &= \sum_{v \in out[u]} \Big(1 + dp_{sum}(v) + dp_{cnt}(v)\Big). \end{aligned} ]

The final answer is \(\sum_{u=1}^{n} dp_{sum}(u)\). It is guaranteed that the directed graph is acyclic.

inputFormat

The first line contains an integer n representing the number of nodes in the tree. The nodes are numbered from 1 to n.

Each of the following n - 1 lines contains two integers u and v, indicating there is a directed edge from u to v in the tree.

outputFormat

Output a single integer, the sum of the lengths of all simple paths in the directed tree.

sample

2
1 2

1