题目背景

原题链接：https://oier.team/problems/X12F。

题目描述

给定一棵 $n$ 个点的树，初始时所有结点为白色。

你可以花费 $w_u$ 的代价将结点 $u$ 染黑。

有 $q$ 次询问，每次询问形如 u l r。对于每次询问，你需要花费尽可能小的代价，将一些结点染黑，使得点 $u$ 到叶结点 $v$ 的简单路径上存在黑色结点，当且仅当 $l \le v \le r$，并输出最小代价。

输入格式

第一行，两个整数 $n, q$，表示结点数量和询问个数。

第二行，$n$ 个整数 $w_1, w_2, \ldots, w_n$，表示将每个结点染黑的代价。

接下来 $n-1$ 行，每行两个整数 $u, v$，表示一条树边。

接下来 $q$ 行，每行三个整数 $u, l, r$，表示一次询问。

输出格式

对于每个询问，输出一行：

若存在满足条件的染色方案，输出最小代价；否则输出 Impossible。

3 4
4 3 1
1 3
3 2
2 1 2
1 2 3
1 1 3
3 1 2

3
1
4
1

7 3
1 -9 1 -9 8 -1 0
1 2
2 3
2 4
4 5
5 6
6 7
1 3 3
1 2 7
1 1 2

1
-19
Impossible

5 5
6 1 4 -6 8
2 4
1 5
3 4
5 4
5 2 3
1 2 3
5 3 3
3 1 5
2 5 5

-6
-6
4
-2
0

提示

【样例解释 #1】

该样例满足特殊性质 A。

对于第一次询问，染黑 $2$ 号点，最小代价为 $3$；

对于第二次询问，染黑 $3$ 号点，最小代价为 $1$；

对于第三次询问，染黑 $1$ 号点，最小代价为 $4$；

对于第四次询问，染黑 $3$ 号点，最小代价为 $1$。

【样例解释 #2】

该样例满足特殊性质 B。

对于第一次询问，染黑 $3$ 号点，最小代价为 $1$；

对于第二次询问，染黑 $2,4,6,7$ 号点，最小代价为 $-19$；

对于第三次询问，可证明没有可行的染色方案。

【数据范围】

本题使用捆绑测试。

对于 $100\%$ 的数据，$1 \le n, q \le 2 \times 10^5$，$|w_u| \le 10^9$，$1 \le u, v \le n$，$1 \le l \le r \le n$。

子任务编号	$n \le$	$q \le$	特殊性质	分值	子任务依赖
$1$	$20$	$20$	无	$5$	-
$2$		$2 \times 10^5$			$1$
$3$	$8000$	$8000$	A		-
$4$			无		$3$
$5$		$2 \times 10^5$	A	$10$
$6$			无		$2, 4, 5$
$7$	$2 \times 10^5$		AB		-
$8$			A	$15$	$5, 7$
$9$			B		$7$
$10$			无	$20$	$6, 8, 9$

特殊性质 A：$w_u \ge 0$。

特殊性质 B：对于所有询问，$u=1$。