P14468 [COCI 2025/2026 #1] 和谐 / Harmonija

本题满分 $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)\lt \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$ 行，每行一个整数，表示答案。

### 样例解释 **样例一解释**：依次染成红、蓝、红、红是一个最优解。 ### 子任务 - $\text{Subtask 1 (27 pts)}$：$n,q\le 15$。 - $\text{Subtask 2 (41 pts)}$：$n,q\le 1000$。 - $\text{Subtask 3 (19 pts)}$：$q\le 10000$。 - $\text{Subtask 4 (23 pts)}$：无额外限制。