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$ 行，每行一个整数，表示答案。

输入输出样例 #1

输入 #1

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

输出 #1

30

输入输出样例 #2

输入 #2

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

输出 #2

4
3
3

说明/提示

样例解释

样例一解释：依次染成红、蓝、红、红是一个最优解。

子任务

• $\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)}$：无额外限制。