Pro.ID1642 TitleDFS 序 3,树上差分 1 Title链接http://10.20.2.8/oj/exercise/problem?problem_id=1642 AC0 Submit0 Ratio- 时间&空间限制描述这是一道模板题。 不保证无快读的程序能过。请务必使用快读。 给一棵有根树,这棵树由编号为 1…N 的 N 个节点组成。根节点的编号为 R 。每个节点都有一个权值,节点 i 的权值为 vi 。 接下来有 M 组操作,操作分为两类:
输入第一行有三个整数 N , M 和 R 。 第二行有 N 个整数,第 i 个整数表示 vi 。 在接下来的 N−1 行中,每行两个整数,表示一条边。 在接下来的 M 行中,每行一组操作。 40%的数据不含操作 3。 对于所有数据,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 行中,每行一组操作。 40%的数据不含操作 3。 对于所有数据,1 ⩽ N , M ⩽ 106 , 1 ⩽ R ⩽ N , −106 ⩽ vi , x ⩽ 106 . Output 对于每组 2 a 操作,输出一个整数,表示节点 a 的权值。 Sample Input Sample #1 Sample Output Sample #1 样例输入Sample #1 样例输出Sample #1 提示作者 |