华师一附中OI组

标题: CF1092F Tree with Maximum Cost [打印本页]

作者: admin 时间: 2021-5-13 17:41
标题: CF1092F Tree with Maximum Cost
https://www.luogu.com.cn/problem/CF1092F

有一棵 n 个节点的树，每个点有一个权值 ai。定义dist(u,v) 为 u,v 两点间距离。
您要找到一个点 u，使得∑dist(i,u)⋅ai最大。您只需求出最大值。
1≤n,ai≤2×10^5。
输入输出样例
输入 #1复制
8
9 4 1 7 10 1 6 5
1 2
2 3
1 4
1 5
5 6
5 7
5 8
输出 #1复制
121
输入 #2复制
1
1337
输出 #2复制
0
说明/提示

欢迎光临华师一附中OI组 (http://hsyit.cn/)