P14657 下弦月

未卡空间\时间的版本。

给定 $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

第一行一个整数 $n$ 代表树上的点数。 第二行 $n$ 个数代表 $w_1,w_2\dots w_n$。 接下来 $n-1$ 行，每行两个整数 $u,v$ 描述了一条树上连接了节点 $u,v$ 的边。 接下来一行一个整数 $q$ 代表了询问的个数。 接下来 $q$ 行，每行两个整数 $l,r$ 代表询问的区间。

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

- 子任务一 $(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$