3662. C - 偏心距
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 给出一棵有 $ n $ 个节点的树，节点 $ i $ 的权值是 $ w_i $ 现在从树上选择一个节点 $ x $ 当作中心，定义偏心距为 $ \textstyle\sum_{i=1}^{n}w_i\timesdis_i $ 其中 $ dis_i $ 表示从节点 $ i $ 到节点 $ x $ 经过的边数 显然，能够使得偏心距最小的中心可能不唯一，所以请你计算这个最小的偏心距 ## 输入格式 第一行输入一个整数 $ n $ ，表示树的节点数 第二行输入 $ n $ 个整数 $ w_1,w_2,⋯,w_n $ ，分别表示每个节点的权值 接下来的 $ n-1 $ 行，每行输入两个整数 $ u $ 和 $ v $ ，表示 $ u $ 点和 $ v $ 点之间有一条边相连 $ 2\len\le2\cdot10^5 $ $ 1\lew_i\le10^8 $ $ 1\leu,v\len,u\nev $ ## 输出格式 输出一个整数代表最小的偏心距 ## 输入 ```in1 4 1 2 3 4 1 2 2 3 3 4 ``` ## 输出 ```out1 8 ``` ```in2 4 3 2 1 4 1 2 2 3 3 4 ``` ```out2 12 ``` ## 提示