U113057 树上游戏

在上古时代，有一个简单的树上游戏。能通关这个游戏的幸运签到者，将会收到一份小礼包。 树上游戏是这样的： 出题人会给挑战者一棵 $n$ 个结点的有根树，每个结点从 $1$ 到 $n$ 编号，有根树的根为 $1$ 号结点。 有根树的每个结点有权值，第 $i$ 个结点的权值为 $w_i$。对于有根树的每个结点，可以定义其深度为该结点到根结点路径上的结点数，第 $i$ 个结点的深度为 $d_i$。 挑战者需要完成的任务是：在有根树上选择一些结点，在满足下述条件的情况下，最大化选择结点的权值和： + 我们称两个**被选择的结点**是**联通**的，当且仅当存在一条以这两个结点为端点的路径，路径上每个点都被选择。 + 对于任意两个联通的点，我们称其属于同一个**联通块**。 + 对于一个联通块，我们要求联通块内任意两个结点之间的深度差的绝对值，不大于给定参数 $k$。 作为挑战者，你需要在最快时间内完成这个任务。

第一行，两个正整数 $n,k$，表示有根树的结点数，给定的参数。 第二行，$n$ 个正整数 $w_1,\dots,w_n$，表示每个结点的权值。 接下来 $n-1$ 行，每行两个整数 $u,v$，表示一条边连接的两个结点的编号。

输出一行一个整数，表示你的答案，即选择结点的权值和的最大值。

对于第一组样例，我们做出如下解释： + 最优方案下选择的结点编号为：$\{1,3,4,5,6\}$。 对于第二组样例，我们做出如下解释 + 最优方案下选择的结点编号为：$\{1,2,3,4,5\}$。 对于所有数据，保证有 $1\leq n\leq 10^6$，$0\leq k\leq n$，$1\leq u,v\leq n$，$0\leq w_i\leq 10^9$。 | **子任务编号** | **分值** | $n\leq$ | $k\leq$ | **特殊性质** | |:--:|:--:|:--:|:--:|:--:| | 1 | 10 | $1000$ | $1000$ | 无 | | 2 | 10 | $10^5$ | $0$ | 无 | | 3 | 10 | $10^5$ | $1$ | 无 | | 4 | 30 | $10^5$ | $10^5$ | 有根树随机生成 | | 5 | 40 | $10^6$ | $10^6$ | 无 |