2025牛客国庆派对day5 K E 个人题解怎么写？

You are given a tree... 树上dp #状态压缩 #随机优化 题目描述 给定一棵带边权的树 \(T=(V,E)\)，其中 \(|V|=n\)，顶点编号为 \(1, 2, \dots, n\)，每个顶点 \(i\) 有一个权值 \(a_i\)。 你需要选择一个顶点子集 \(S \subseteq V\)，满足 \(S\) 中最多包含 \(k\) 个顶点，并且这些顶点的权值 \(a_i\) 互不相同。目标是最大化被“覆盖”的边的权重之和。一条边 \(e\) 被“覆盖”当且仅当存在 \(u, v \in S\)，使得 \(e\) 位于 \(u\) 到 \(v\) 的唯一路径上。 输入描述 第一行包含两个整数 \(n, k\) \((1 \le n \le 5000, 2 \le k \le 5)\)，分别表示树的大小和子集 \(S\) 的最大大小。 第二行包含 \(n\) 个整数 \(a_1, a_2, \dots, a_n\) \((1 \le a_i \le n)\)，表示每个顶点的权值。 接下来 \(n-1\) 行，每行包含三个整数 \(u, v, w\) \((1 \le u, v \le n, -10^9 \le w \le 10^9)\)，表示树中有一条连接 \(u\) 和 \(v\)、权重为 \(w\) 的边。 输出描述 输出一行一个整数，表示被“覆盖”边的权重之和的最大值。