TouchStone
  Please Login
Login Sign Up
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P6523
  • Problem
  • P6523[DFS序基础]链修改,链查询
    Limits : Time Limit : 3000 MS   Memory Limit : 262144 KB
    Judgment Tips : 3s,256MB
    Description

    一棵$n$个节点的有根树,节点编号$1\sim n$,其中$1$是根节点,每个节点上有权值,$m$次操作:

    • 1 a b c:将a,b链上的每个节点权值增加c
    • 2 a b:查询a,b链上的权值之和
    Input Format

    第一行两个整数$n,m$。

    第二行$n$个整数,表示每个节点的初始权值。

    第三行$n-1$个整数,表示$2\sim n$节点的父亲编号。

    接下来$m$行,每行一个形如“1 a b c”或者“2 a b”的操作。

    Output Format

    每次查询输出一行答案。

    Sample Input 1

    10 10
    6 9 10 9 7 9 6 10 8 4
    1 1 3 4 5 6 4 8 7
    1 6 4 3
    2 1 10
    1 2 5 9
    1 7 6 3
    1 4 2 1
    2 10 2
    1 5 5 9
    2 3 5
    2 8 4
    2 6 6

    Sample Output 1

    60
    124
    70
    32
    15

    Sample Input 2

    5 5
    1 2 3 4 5
    1 1 3 3
    1 1 3 10
    2 2 5
    1 5 4 20
    2 1 4
    2 2 5

    Sample Output 2

    31
    68
    71

    Hint

    $1\leq n,m,\texttt{初始权值},c\leq 10^6$