Edge Strength :
Difficulty Level : Medium
Submissions : 191
Asked In :
Marks :15
: 6 | : 0
We have a tree with $$$N$$$ vertices numbered $$$1,2,…,N.$$$
The $$$i^{th}$$$ edge $$$(1 \le i \le N−1)$$$ connects Vertex $$$u_i$$$ and Vertex $$$v_i$$$ and has a weight $$$w_i$$$.
For different vertices $$$u$$$ and $$$v$$$, let $$$f(u,v)$$$ be the greatest weight of an edge contained in the shortest path from Vertex $$$u$$$ to Vertex $$$v$$$.
Your task is to find $$$$$$\sum_{1 \le i \lt j \le N} f(i,j) $$$$$$ More formally, Please find the sum of the maximum weighted edge over all paths of the tree.
The first line of input contains an integer $$$N$$$ $$$(2 \le N \le 10^5)$$$ — the number of nodes in the tree.
The next $$$N-1$$$ lines contain $$$3$$$ space separated integers each $$$u_i$$$, $$$v_i$$$ $$$(1 \le u_i,v_i\le N)$$$ and $$$w_i$$$ $$$(1 \le w_i \le 10^7)$$$ denoting an edge of weight $$$w_i$$$ between vertices $$$u_i$$$ and $$$v_i$$$.
Print a single integer — the answer to the problem in a single line.
3 1 2 10 1 3 2
22
5 1 2 4 2 3 1 1 4 6 4 5 12
75
In sample test case 1,
- $$$f(1,2) = 10$$$
- $$$f(1,3) = 2$$$
- $$$f(2,3) = 10$$$
In sample test case 2,
- $$$f(2,3) = 1$$$
- $$$f(1,2) = f(1,3) = 4$$$
- $$$f(1,4) = f(2,4) = f(3,4) = 6$$$
- $$$f(1,5) = f(2,5) = f(3,5) = f(4,5) = 12$$$
