You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小镇里有 $n$ 个地点，通过 $n-1$ 条道路连通，每条道路长 $1$ 。两个被某条道路直接相连的地点被称为相邻地点。也就是说，所有地点构成一棵包含 $n$ 个节点的树。 小镇要筹办 $q$ 场奇迹之夜的活动。每个地点具有正整数的日常人气 $m_i$ 和聚会人气 $w_i$ 。另外，小镇里有一个车站位于点 $k$ ，车站的交通范围为 $L$ 。 活动时，每个地点（包括车站在内）需要选择三项之一：

举办日常活动：该地点活动的人气为它的日常人气 $m_i$ 。 举办聚会活动：该地点活动的人气为它的聚会人气 $w_i$ 。要举办聚会，要么它至少有一个相邻地点成为后勤基地，要么它离车站即 $k$ 号地点的距离（两点之间的最小道路数）不超过交通范围 $L$ 。 成为后勤基地：人气为零，但是相邻地点可以举办聚会。

一场活动中小镇的总人气为所有地点的人气之和。 每场活动中车站的交通范围 $L$ 可能不同，其余信息都相同。你需要求出每次活动最大可能的小镇总人气。

输入格式

请注意这道题需要使用文件输入输出，例如 freopen。文件名见题目标题下方的评测信息。 第一行两个整数 $n, q$ ，表示地点个数和活动场数； 第二行 $n$ 个整数，其中第 $i$ 个表示 $i$ 号地点的日常人气 $m_i$ ； 第三行 $n$ 个整数，其中第 $i$ 个表示 $i$ 号地点的聚会人气 $w_i$ ； 第四行一个整数 $k$ ，表示车站所在的地点。 接下来 $n-1$ 行，每行两个整数 $u,v$ ，表示有一条道路连接 $u,v$ 。保证任意两地点可以通过道路直接或间接连通。 接下来 $q$ 行，其中第 $i$ 行包含一个整数 $L_i$ ，表示第 $i$ 次活动中车站的交通范围 $L_i$ 。

输出格式

请注意这道题需要使用文件输入输出，例如 freopen。文件名见题目标题下方的评测信息。 输出共 $q$ 行，其中第 $i$ 行一个整数，表示第 $i$ 次活动最大可能的小镇总人气。

样例

样例输入 1

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

样例输出 1

42
50
52

样例 2、3、4

见。

数据范围与提示

对于 $100\%$ 的数据， $1 \leq n, q \leq 10^5,0\le L_i\le 10^5,1 \leq m_i, w_i \leq 10^9$ 一共有 $20$ 个测试点。部分测试点满足的性质如下：

$1,2$ 号： $w_i=1$ ； $3,4$ 号： $q=1, L_1=n$ ； $1,2,3,4,5,6$ 号： $1\leq n,q \leq 10$ ； $1,2,3,4,5,6,7,8,9,10,11,12,13,14$ 号： $1 \leq n, q\leq 5000$ ；