题目背景

未卡空间\时间的版本。

题目描述

给定 $n$ 个点的一棵树，每个点有权值 $w_i$。

有 $q$ 次询问，每次给定 $l,r$，你需要求出仅保留树上编号在 $l,r$ 内的点形成的森林的最大权独立集的值。

形式化的，你需要选出点集 $\{x_1,x_2\dots x_k\}$，满足：

• $l\leq x_i\leq r$。
• $\forall 1\leq i<j\leq k,x_i$ 和 $x_j$ 在树上没有边相连。

求出满足上述条件的所有点集中 $\sum w_{x_i}$ 的最大值。

输入格式

第一行一个整数 $n$ 代表树上的点数。

第二行 $n$ 个数代表 $w_1,w_2\dots w_n$。

接下来 $n-1$ 行，每行两个整数 $u,v$ 描述了一条树上连接了节点 $u,v$ 的边。

接下来一行一个整数 $q$ 代表了询问的个数。

接下来 $q$ 行，每行两个整数 $l,r$ 代表询问的区间。

输出格式

共 $q$ 行，每行一个非负整数代表该询问的答案。

4
2 8 5 9
1 2
1 3
3 4
4
1 2
2 4
1 3
4 4

8
17
13
9

提示

• 子任务一 $(5\%)$ ：$n,q\leq 5000$。
• 子任务二 $(10\%)$ ：$\sum r-l\leq 10^7$。
• 子任务三 $(15\%)$ ：$n\leq 2\times 10^4$。
• 子任务四 $(15\%)$ ：$n\leq 5\times 10^4$。
• 子任务五 $(15\%)$ ：树是一条链。
• 子任务六 $(15\%)$ ：若以 $1$ 号结点为根，则每个结点 $x(x>1)$ 的父亲在 $1\sim x-1$ 里随机生成。
• 子任务七 $(25\%)$ ：无特殊限制。

对于 $100\%$ 的数据，$1\leq n,q\leq 10^5,0\leq w_i\leq 10^5,1\leq l\leq r\leq n$