展厅规划 (exhi)

题目描述

Y 同学作为一名艺术策展人，正筹备在一座特殊的艺术馆内举办一场展览。这座艺术馆由 $n$ 个展厅组成，展厅之间通过 $n-1$ 条双向通道连接，形成了一个典型的树形结构。

每个展厅 $i$ 都有其独特的学术价值 $w_i$ 和所属的艺术主题分类 $c_i$。为了保证观众的观展体验和建筑安全，Y 同学在挑选用于展览的展厅集合 $S$ 时，必须遵守以下规定：

1. 安全距离限制：为了防止人流过于拥挤，集合 $S$ 中的任意两个展厅之间不能有直接的通道相连（即集合 $S$ 必须是原图的一个独立集）。
2. 主题多样性限制：为了丰富展览内容，集合 $S$ 中所有展厅的艺术主题必须互不相同（即对于 $u, v \in S$ 且 $u \neq v$，需满足 $c_u \neq c_v$）。

Y 同学希望选出的展厅集合 $S$ 的学术价值总和最大。请你编写一个程序，帮助 Y 同学计算出这个最大价值总和。

输入格式

第一行包含两个正整数 $n$ 和 $C$，分别表示展厅的总数和艺术主题的总数。

第二行包含 $n$ 个正整数 $w_1, w_2, \ldots, w_n$，表示每个展厅的学术价值。

第三行包含 $n$ 个正整数 $c_1, c_2, \ldots, c_n$，表示每个展厅所属的主题编号。

接下来的 $n - 1$ 行，每行包含两个正整数 $u_j$ 和 $v_j$，表示展厅 $u_j$ 与 $v_j$ 之间存在一条通道。

输出格式

输出一行一个整数，表示在满足所有限制条件下的最大学术价值总和。

样例

样例输入 #1

4 4
1 1 1 1
1 2 3 4
1 2
1 3
1 4

样例输出 #1

3

样例输入 #2

5 3
5 1 2 3 1
1 2 2 3 1
1 2
1 3
2 4
2 5

样例输出 #2

8

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le n \le 1000$，$1 \le C \le 10$，$1 \le w_i \le 10^{9}$，$1 \le c_i \le C$。

• 特殊性质 A：保证给定的树结构退化为一条链，即每个结点的度数不超过 $2$。
• 特殊性质 B：保证给定的树为一个菊花图，即存在一个结点 $u$，使得其余 $n-1$ 个结点均与 $u$ 直接相连。