# Sum of Distances in a Tree
## Problem Statement
You are given a tree consisting of $n$ nodes. The nodes are numbered from $1$ to $n$.
Let $d(u, v)$ denote the distance between nodes $u$ and $v$, which is defined as the number of edges in the unique path connecting $u$ and $v$.
Your task is to find the sum of distances $d(u, v)$ for all distinct unordered pairs of nodes $\{u, v\}$ such that $u \ne v$. That is, you need to calculate $\sum_{1 \le u < v \le n} d(u, v)$.
## Input Format
The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$), representing the number of nodes in the tree.
The next $n-1$ lines each contain two integers $a$ and $b$ ($1 \le a, b \le n$), indicating that there is an edge between nodes $a$ and $b$.
## Output Format
Print a single integer, the total sum of distances over all distinct unordered pairs of nodes.
## Sample Test Cases
### Sample Input 1
```
5
1 2
1 3
3 4
3 5
```
### Sample Output 1
```
18
```
### Sample Input 2
```
4
1 2
2 3
3 4
```
### Sample Output 2
```
10
```
## Constraints
- $1 \le n \le 2 \cdot 10^5$
- $1 \le a, b \le n$
- The given edges form a valid tree.
- Time limit: 1 second
- Memory limit: 256 MB
## Explanation
The total sum of distances $\sum_{1 \le u < v \le n} d(u, v)$ can be calculated by considering the contribution of each edge to the total sum.
For any edge $e = (x, y)$ in the tree, if we remove this edge, the tree splits into two connected components. Let $s$ be the number of nodes in the component containing $x$ (when viewed from $y$, or vice-versa), and $n-s$ be the number of nodes in the other component. Any path between a node in the first component and a node in the second component must pass through the edge $e$. There are $s \times (n-s)$ such distinct unordered pairs of nodes. Thus, the edge $e$ contributes $s \times (n-s)$ to the total sum of distances.
By summing $s \times (n-s)$ for all edges in the tree, we get the total sum of distances $\sum_{1 \le u < v \le n} d(u, v)$.
For Sample Input 1 ($n=5$):
The tree structure is:
1 -- 2
|
3 -- 4
|
5
We can perform a Depth First Search (DFS) starting from an arbitrary root (e.g., node 1) to calculate the subtree size for each node. When traversing an edge $(parent, child)$, the subtree size of $child$ (including $child$ itself) is $s$. The other component has $n-s$ nodes.
1. **Edge (1, 2)**: The subtree rooted at 2 has size $s=1$. The other component has $n-s = 5-1=4$ nodes. Contribution: $1 \times (5-1) = 4$.
2. **Edge (1, 3)**: The subtree rooted at 3 (which includes 3, 4, 5) has size $s=3$. The other component has $n-s = 5-3=2$ nodes. Contribution: $3 \times (5-3) = 6$.
3. **Edge (3, 4)**: The subtree rooted at 4 has size $s=1$. The other component has $n-s = 5-1=4$ nodes. Contribution: $1 \times (5-1) = 4$.
4. **Edge (3, 5)**: The subtree rooted at 5 has size $s=1$. The other component has $n-s = 5-1=4$ nodes. Contribution: $1 \times (5-1) = 4$.
Total sum $= 4 + 6 + 4 + 4 = 18$.
For Sample Input 2 ($n=4$):
The tree is a path graph: $1-2-3-4$.
1. **Edge (1, 2)**: Subtree rooted at 2 (relative to 1) has size $s=3$ (nodes 2, 3, 4). Other component size $n-s = 4-3=1$. Contribution: $3 \times (4-3) = 3$.
2. **Edge (2, 3)**: Subtree rooted at 3 (relative to 2) has size $s=2$ (nodes 3, 4). Other component size $n-s = 4-2=2$. Contribution: $2 \times (4-2) = 4$.
3. **Edge (3, 4)**: Subtree rooted at 4 (relative to 3) has size $s=1$ (node 4). Other component size $n-s = 4-1=3$. Contribution: $1 \times (4-1) = 3$.
Total sum $= 3 + 4 + 3 = 10$.
Loading problem statement...