Pro.ID1640 TitleDFS 序 1 Title链接http://10.20.2.8/oj/exercise/problem?problem_id=1640 AC1 Submit1 Ratio100.00% 时间&空间限制描述这是一道模板题。 给一棵有根树,这棵树由编号为 1…N 的 N 个节点组成。根节点的编号为 R 。每个节点都有一个权值,节点 i 的权值为 vi 。 接下来有 M 组操作,操作分为两类:
输入第一行有三个整数 N , M 和 R 。 第二行有 N 个整数,第 i 个整数表示 vi 。 在接下来的 N−1 行中,每行两个整数,表示一条边。 在接下来的 M 行中,每行一组操作。 1 ⩽ N , M ⩽ 106 , 1 ⩽ R ⩽ N , −106 ⩽ vi ,x ⩽ 106 . 输出Description 这是一道模板题。 给一棵有根树,这棵树由编号为 1…N 的 N 个节点组成。根节点的编号为 R 。每个节点都有一个权值,节点 i 的权值为 vi 。 接下来有 M 组操作,操作分为两类:
Input 第一行有三个整数 N , M 和 R 。 第二行有 N 个整数,第 i 个整数表示 vi 。 在接下来的 N−1 行中,每行两个整数,表示一条边。 在接下来的 M 行中,每行一组操作。 1 ⩽ N , M ⩽ 106 , 1 ⩽ R ⩽ N , −106 ⩽ vi ,x ⩽ 106 . Output 对于每组 2 a 操作,输出一个整数,表示「以节点 a 为根的子树」上所有节点的权值之和。 Sample Input 10 14 9 Sample Output 21 样例输入10 14 9 样例输出21 提示作者 |