BZPRO
#5111. Tree
内存限制：512 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
给一棵n个结点的树，每个结点有一个正整数权值。要求选出一个结点的集合，满足：
1.这个集合包含1号结点
2.这个集合在树上是一个连通块。
即，设这个集合为S，则树上存在|S|-1条边，这些边连接的结点都属于S。
记一个集合的权值为该集合内所有结点的权值和。
求权值第k小的集合的权值。
输入格式
第一行两个整数n,k。
接下来n-1行，每行两个整数u,v，表示结点u和结点v之间有一条边。
接下来一行n个整数，表示每个结点的权值。
保证存在权值第k小的集合
对于60%的数据，n<=300000,k<=600000
对于另外40%数据，n<=100000,10^6<=k<=10^18,保证答案不超过500
输出格式
一个整数，表示答案
样例
样例输入
5 7
1 2
2 3
2 4
4 5
1 2 3 4 5
样例输出
15
数据范围与提示
BZPRO