Pro.ID1607 Title树链剖分 Title链接http://10.20.2.8/oj/exercise/problem?problem_id=1607 AC4 Submit4 Ratio100.00% 时间&空间限制描述这是一道模板题。 给定一棵 n 个节点的树,初始时该树的根为 1 号节点,每个节点有一个给定的权值。下面依次进行 m 个操作,操作分为如下五种类型:
输入第一行为一个整数 n,表示节点的个数。 第二行 n 个整数表示第 i 个节点的初始权值 ai 。 第三行 n−1 个整数,表示 i+1 号节点的父节点编号 fi+1 ( 1 ⩽ fi+1 ⩽ n )。 第四行一个整数 m,表示操作个数。 接下来 m 行,每行第一个整数表示操作类型编号:( 1 ⩽ u , v ⩽ n )
对于 100% 的数据,1 ⩽ n, m, k, ai ⩽ 105 。数据有一定梯度。 输出Description 这是一道模板题。 给定一棵 n 个节点的树,初始时该树的根为 1 号节点,每个节点有一个给定的权值。下面依次进行 m 个操作,操作分为如下五种类型:
Input 第一行为一个整数 n,表示节点的个数。 第二行 n 个整数表示第 i 个节点的初始权值 ai 。 第三行 n−1 个整数,表示 i+1 号节点的父节点编号 fi+1 ( 1 ⩽ fi+1 ⩽ n )。 第四行一个整数 m,表示操作个数。 接下来 m 行,每行第一个整数表示操作类型编号:( 1 ⩽ u , v ⩽ n )
对于 100% 的数据,1 ⩽ n, m, k, ai ⩽ 105 。数据有一定梯度。 Output 对于每一个类型为 4 或 5 的操作,输出一行一个整数表示答案。 Sample Input 6 Sample Output 15 样例输入6 样例输出15 提示作者 |