g7-07686. 子树查询 · 林老师的题库

题目描述

给定一棵以 $1$ 号结点为根的树，结点编号为 $1 \sim n$ ，第 $i$ 个结点有一个非负整数点权 $w_{i}$ 。

一个结点 $x$ 的子树，指的是 $x$ 本身以及它的所有后代结点组成的集合。

现在有 $q$ 次询问，每次询问给出一个操作类型 $o p$ 和一个结点 $x$ ：

第一行一个正整数 $n$ ，表示树的结点数。

第二行 $n$ 个非负整数 $w_{1}, w_{2}, \dots, w_{n}$ ，依次表示每个结点的点权。

接下来 $n - 1$ 行，每行两个正整数 $u, v$ ，表示结点 $u$ 与结点 $v$ 之间有一条边；当 $n = 1$ 时没有边。保证这些边构成一棵以 $1$ 号结点为根的树。

接下来一行一个正整数 $q$ ，表示询问次数。

接下来 $q$ 行，每行两个整数 $o p, x$ ，表示一次询问，其中 $o p \in {1, 2}$ ， $1 \leq x \leq n$ 。

共 $q$ 行，每行一个整数，依次表示每次询问的答案。

输入：

6
2 5 1 4 3 6
1 2
1 3
2 4
2 5
3 6
5
1 1
2 2
1 3
2 4
2 1

输出：

样例说明：

以 $1$ 为根时，各结点的子树如下：

因此前四次询问的答案依次为 $6, 12, 2, 4$ ，最后一次询问结点 $1$ 的权值和为 $21$ 。