8127: BZOJ4127:Abs

Memory Limit:256 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

 给定一棵树,设计数据结构支持以下操作

    1 u v d  表示将路径 (u,v) 加d

    2 u v  表示询问路径 (u,v) 上点权绝对值的和


输入格式

第一行两个整数n和m,表示结点个数和操作数

接下来一行n个整数a_i,表示点i的权值

接下来n-1行,每行两个整数u,v表示存在一条(u,v)的边

接下来m行,每行一个操作,输入格式见题目描述


输出格式

对于每个询问输出答案


样例输入

    4 4
    -4 1 5 -2
    1 2
    2 3
    3 4
    2 1 3
    1 1 4 3
    2 1 3
    2 3 4

样例输出

    10
    13
    9

提示

对于100%的数据,n,m <= 10^5 且 0<= d,|a_i|<= 10^8


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: