# Minimum Edge Weight Path Sum
## Problem Statement
You are given a weighted tree with $n$ nodes. For any two distinct nodes $u$ and $v$, let $D(u,v)$ be defined as the minimum weight of an edge in the unique simple path between node $u$ and node $v$. Your task is to find the summation of $D(u,v)$ for all ordered pairs $(u,v)$ such that $1 \le u < v \le n$.
## Input Format
The first line of input contains a single integer $n$ ($1 \le n \le 10^5$) \u2014 the number of nodes in the tree.
The next $n-1$ lines each contain three space-separated integers $u, v, w$ ($1 \le u, v \le n$, $1 \le w \le 10^9$) \u2014 denoting an edge between node $u$ and node $v$ with weight $w$.
## Output Format
Print a single integer representing the total sum $\sum_{1 \le u < v \le n} D(u,v)$.
## Sample Test Cases
### Sample Input 1
```
5
1 2 1
2 3 5
3 4 3
4 5 2
```
### Sample Output 1
```
21
```
### Sample Input 2
```
5
1 2 5
1 3 4
2 4 1
3 5 2
```
### Sample Output 2
```
23
```
## Constraints
- $1 \le n \le 10^5$
- $1 \le u, v \le n$
- $1 \le w \le 10^9$
- The given graph is guaranteed to be a tree.
- Time limit: 4 seconds
- Memory limit: 512 MB
## Explanation
To calculate the sum $\sum_{1 \le u < v \le n} D(u,v)$ efficiently, consider the contribution of each edge weight. If we process the edges in descending order of their weights, we can use a Disjoint Set Union (DSU) data structure.
When an edge with weight $w$ connecting two nodes $u'$ and $v'$ is considered, suppose $u'$ is in a component of size $a$ and $v'$ is in a component of size $b$. Before this edge is added, these two components were disconnected. When this edge is added, it merges these two components. For any pair of nodes $(x, y)$ where $x$ is from the component containing $u'$ and $y$ is from the component containing $v'$, the unique simple path between $x$ and $y$ *must* pass through the newly added edge $(u', v')$. Since we are processing edges in descending order of weight, this edge $(u', v')$ with weight $w$ will be the minimum weight edge on the path between $x$ and $y$ (because any other edge on the path would have been either part of the existing components, or an edge with weight greater than or equal to $w$ which would have been processed earlier and formed a path without $w$ being the bottleneck, or an edge with weight less than $w$ which would have been processed later and not yet connected these components).
Therefore, this edge of weight $w$ contributes $a \times b \times w$ to the total sum, as there are $a \times b$ such pairs $(x, y)$ that become connected with $w$ as their minimum path edge weight. We sum these contributions as we process and merge components using DSU.
Loading problem statement...