第 4 题和谐 (`harmonija`)

时间限制 1.0 s · 空间限制 256 MB · 111 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 harmonija.in，输出文件 harmonija.out。

本题满分 110。

题目描述

给定一棵 $n$ 个点的树，每个点有红权值 $c_i$ 和蓝权值 $p_i$ 。

$q$ 次独立询问，每次询问给定 $u, v$ ，设 $u, v$ 最短路上的点依次为 $s_1, s_2, \ldots, s_k$ 。你需要依次将 $s_1, s_2, \ldots, s_k$ 染成红色或者蓝色，满足：

对于 $i = 1, 2, \ldots, k$ ，在染色 $s_1 \sim s_i$ 时，设有 $x$ 个红点， $y$ 个蓝点，则 $\max(x, y) < \min(x, y) + 3$ 。

对于每次询问，求出满足条件的染色方案中，所有蓝点的蓝点权和红点的红点权之和的最大值。形式化地说，你需要求出

\sum_{1 \le i \le k,\ s_i \text{ is red vertex}} c_{s_i} + \sum_{1 \le i \le k,\ s_i \text{ is blue vertex}} p_{s_i}

的最大值。

根据定义，可以证明符合条件的路径总是存在。

第一行，两个正整数 $n, q$ （ $1 \le n, q \le 10^5$ ）。

第二行， $n$ 个整数 $c_i$ （ $-10^9 \le c_i \le 10^9$ ）。

第三行， $n$ 个整数 $p_i$ （ $-10^9 \le p_i \le 10^9$ ）。

接下来 $(n - 1)$ 行，每行两个正整数 $u, v$ （ $1 \le u, v \le n, u \neq v$ ），描述一条树边。保证输入形成树。

接下来 $q$ 行，每行两个正整数 $u, v$ （ $1 \le u, v \le n$ ），描述一次询问。

输出 $q$ 行，每行一个整数，表示答案。

输入：

4 1
10 10 10 10
-10 0 -10 0
1 2
2 3
3 4
1 4

输出：

输入：

5 3
-5 -4 0 -3 3
3 1 -5 0 0
3 2
1 4
3 5
1 2
2 5
1 4
5 3

输出：

4
3
3