P7484.md

再生之青

题目描述

YSGH 有一个大小为 $n$ 的树和一个长度为 $m$ 的序列。

树上每个点 $i$ 有颜色 $c_i$ 和价值 $a_i$，颜色两两不同，保证叶子个数不超过 $\boldsymbol{20}$。

序列第 $i$ 个位置也有一个颜色 $d_i$ 和价值 $b_i$，颜色也两两不同（但树和序列颜色可能会相同）。

YSGH 想从树上选一条链和序列的一个区间满足一个颜色最多只能出现一次，他想知道他能选出来的最大的价值和。

输入格式

第一行，两个正整数 $n, m$，分别表示树的大小和序列长度。

接下来 $n - 1$ 行，每行两个正整数 $x, y$，表示树上的一条边。

接下来一行，每行 $n$ 个正整数，第 $i$ 个表示 $c_i$。

接下来一行，每行 $n$ 个正整数，第 $i$ 个表示 $a_i$。

接下来一行，每行 $m$ 个正整数，第 $i$ 个表示 $d_i$。

接下来一行，每行 $m$ 个正整数，第 $i$ 个表示 $b_i$。

输出格式

仅一行，一个整数，表示答案。

样例 #1

样例输入 #1

4 4
1 2
2 3
3 4
1 2 3 4
10 2 3 7
2 5 6 1
5 1 7 2

样例输出 #1

30

提示

【样例解释】

最优方案是选择树的 $1, 2, 3, 4$ 号节点和序列的第 $2, 3$ 个位置。

价值和是 $10 + 2 + 3 + 7 + 1 + 7 = 30$。

---

【数据范围】

本题采用捆绑测试。

对于 $100 %$ 的数据，$1 \le n \le 5 \times {10}^4$，$1 \le m \le 5 \times {10}^5$，$1 \le c_i, d_i \le n + m$，$1 \le a_i, b_i \le {10}^9$，保证树的叶子个数不超过 $20$。

• Subtask 1（10 points）: $n, m \le 500$。
• Subtask 2（10 points）: $n, m \le 1000$。
• Subtask 3（10 points）: $n, m \le 5000$。
• Subtask 4（20 points）: 满足树的第 $i$ 条边连接的是 $i$ 和 $i + 1$。
• Subtask 5（15 points）: $m \le {10}^5$。
• Subtask 6（35 points）: 无特殊限制。