树的中心(Center of Tree)

题目描述

给定一个树形网络，在该网络中，有 n 个点，n-1 条道路，这些道路都是可以双向通行的，这些道路可以连通所有的点。但注意，每条道路的两个方向可能有不同的距离权重，也就是说，假设一条道路连通了点 u 与点 v，则 u 到 v 的距离权重不一定等于 v 到 u 的距离权重。

请找出一个点，作为网络的中心，使得从这个中心出发，散到 每个点的距离之和达到最小，输出这个最小值。

（注意这个问题不是聚到中心，而是从中心散到各点的最小距离）

输入格式

第一行：单个正整数 n；

第二行到第 n 行：每行四个整数 uᵢ，vᵢ，aᵢ，bᵢ，表示一条道路连通了 uᵢ 与 vᵢ，且 uᵢ 到 vᵢ 的权重为 aᵢ，vᵢ 到 uᵢ 的权重为 bᵢ。

输出格式

单个正整数：表示一个最小的距离之和。

数据范围

• 对于 30% 的数据，1 ≤ n ≤ 300；
• 对于 60% 的数据，1 ≤ n ≤ 5000；
• 对于 100% 的数据，1 ≤ n ≤ 100,000。
• 1 ≤ aᵢ,bᵢ ≤ 1,000,000。

样例输入 #1

4 1 4 10 2 2 4 9 12 3 4 2 8

样例输出 #1

20

说明：以1为中心，距离之和为50；以2为中心，距离之和为37；以3为中心，距离之和为20；以4为中心，距离之和为22。

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐。

测试点分布