{"problem":{"name":"F. Minimize Tree","description":{"content":"Given a weighted undirected tree of N nodes, rooted at the node 1. You can remove at most 1 edge and add another edge of same weight such that the resulting graph is still a tree. Minimize the sum of ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10105F"},"statements":[{"statement_type":"Markdown","content":"Given a weighted undirected tree of N nodes, rooted at the node 1. You can remove at most 1 edge and add another edge of same weight such that the resulting graph is still a tree. Minimize the sum of distances from node 1 to all other nodes.\n\nThe first line contains a single integer N, the size of the tree. Next N - 1 lines contain three space separated integers u, v and w, denoting an edge between the vertices u and v of weight w.\n\n*Constraints:* 1 ≤ N ≤ 5 × 104, 1 ≤ u, v ≤ N,  - 103 ≤ w ≤ 103\n\nOutput a single integer, the minimum sum of distances from node 1 to all other nodes.\n\n## Input\n\nThe first line contains a single integer N, the size of the tree. Next N - 1 lines contain three space separated integers u, v and w, denoting an edge between the vertices u and v of weight w.*Constraints:* 1 ≤ N ≤ 5 × 104, 1 ≤ u, v ≤ N,  - 103 ≤ w ≤ 103\n\n## Output\n\nOutput a single integer, the minimum sum of distances from node 1 to all other nodes.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T = (V, E) $ be a weighted undirected tree with $ |V| = N $, rooted at node $ 1 $.  \nLet $ w(e) \\in \\mathbb{Z} $ denote the weight of edge $ e \\in E $, with $ |E| = N - 1 $.  \nLet $ d_T(u, v) $ denote the shortest path distance between nodes $ u $ and $ v $ in $ T $.  \nLet $ D_T = \\sum_{v \\in V \\setminus \\{1\\}} d_T(1, v) $ be the total distance from root $ 1 $ to all other nodes in $ T $.\n\n**Constraints**  \n1. $ 1 \\leq N \\leq 5 \\times 10^4 $  \n2. For each edge $ (u, v, w) \\in E $: $ 1 \\leq u, v \\leq N $, $ -10^3 \\leq w \\leq 10^3 $  \n3. Exactly one edge $ e \\in E $ may be removed, and one edge $ e' \\notin E $ of weight $ w(e) $ may be added, such that the resulting graph is still a tree.\n\n**Objective**  \nMinimize $ D_{T'} = \\sum_{v \\in V \\setminus \\{1\\}} d_{T'}(1, v) $ over all valid transformations $ T' $ of $ T $, where $ T' $ is obtained by replacing one edge $ e \\in E $ with another edge $ e' $ of the same weight such that $ T' $ remains a tree.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10105F","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}