#P3302. [Shoi2005]树的双中心

    ID: 678 传统题 1000ms 512MiB 尝试: 360 已通过: 136 难度: 7 上传者: 标签>难度分类提高+/省选-枚举与搜索暴力枚举图论树上加权中位点动态规划树形 DP模拟与实现技巧增量维护CF2300

[Shoi2005]树的双中心

题目描述

给定一棵树 T=(V,E)T=(V,E)。每个节点 vv 都有一个正整数权值 W(v)W(v)。两节点间的距离 d(u,v)d(u,v) 是连接它们的唯一简单路径所经过的边数,约定 d(v,v)=0d(v,v)=0。

选出两个不同的节点 x,yx,y 作为中心,最小化

S(x,y)=∑v∈VW(v)min⁡{d(v,x),d(v,y)}.S(x,y)=\sum_{v\in V}W(v)\min\{d(v,x),d(v,y)\}.

输入格式

从标准输入读取。第一行是节点数 NN,节点编号为 11 到 NN。接下来 N−1N-1 行,每行两个整数 u,vu,v,表示一条连接这两个节点的无向边。

随后 NN 行每行一个正整数,第 ii 个数是 W(i)W(i)。

输出格式

向标准输出写入一行一个整数,表示 S(x,y)S(x,y) 的最小值。

样例 1

5
1 2
1 3
3 4
3 5
5
7
6
5
4
14

样例说明

可以选择 22 和 33 为两个中心,得到最小值 1414。

数据范围

2≤N≤500002\le N\le50000,树的深度不超过 100100,最优值不超过 10910^9。