题目描述
给定 $n$ 个节点的树（根为 $1$），第 $i$ 个节点初始点权为 $w_i$。支持两种操作共 $q$ 次：操作一，把路径 $u$ 到 $v$ 上所有点的点权加 $w$；操作二，查询路径 $u$ 到 $v$ 上所有点的权值和。请用树链剖分等高效方法求解。
输入格式
第一行两个整数 $n,q$；第二行 $n$ 个整数 $w_i$；接下来 $n-1$ 行每行一条树边；最后 $q$ 行，每行是 1 u v w 或 2 u v。
输出格式
对每个操作二输出一行一个整数。
数据范围
$$1 \le n,q \le 10^5,\ |w_i|,|w| \le 10^6$$