{"problem":{"name":"Sum of Maximum Weights","description":{"content":"We have a tree with $N$ vertices numbered $1, 2, \\dots, N$.   The $i$\\-th edge $(1 \\leq i \\leq N - 1)$ connects Vertex $u_i$ and Vertex $v_i$ and has a weight $w_i$. For different vertices $u$ and $v$","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc214_d"},"statements":[{"statement_type":"Markdown","content":"We have a tree with $N$ vertices numbered $1, 2, \\dots, N$.  \nThe $i$\\-th edge $(1 \\leq i \\leq N - 1)$ connects Vertex $u_i$ and Vertex $v_i$ and has a weight $w_i$.\nFor 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$.\nFind $\\displaystyle \\sum_{i = 1}^{N - 1} \\sum_{j = i + 1}^N f(i, j)$.\n\n## Constraints\n\n*   $2 \\leq N \\leq 10^5$\n*   $1 \\leq u_i, v_i \\leq N$\n*   $1 \\leq w_i \\leq 10^7$\n*   The given graph is a tree.\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$u_1$ $v_1$ $w_1$\n$\\vdots$\n$u_{N - 1}$ $v_{N - 1}$ $w_{N - 1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc214_d","tags":[],"sample_group":[["3\n1 2 10\n2 3 20","50\n\nWe have $f(1, 2) = 10$, $f(2, 3) = 20$, and $f(1, 3) = 20$, so we should print their sum, or $50$."],["5\n1 2 1\n2 3 2\n4 2 5\n3 5 14","76"]],"created_at":"2026-03-03 11:01:13"}}