11563: 【原1563】柏爷神树数据加强版

题目

题目描述

author: Taring Lee 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1563

Description

Taring表示柏爷神树是一种柏树。

这是一棵有N个节点的有根数，根的编号是1。每个节点有一个初始权值。

紧接着我们会对这棵神树做M次操作，操作分两种：

• 1 xvalue 表示将节点x的权值加上value，节点x的子节点全部减去value，节点x的子节点的子节点全部加上value ... 以此类推。也就是说，对于一个在以节点x为根的子树上的节点y，它若经过偶数条边到达节点x，则给y的权值加上value，否则减去value。
• 2 x 询问节点x当前的权值是多少。

请编写一个程序回答所有的询问。

Input Format

输入数据第一行是两个整数N和M。

接下来一行，总共有N个整数。第i个整数表示节点i的初始权值。

接下来N-1行，每行有两个数u,v。表示节点u和节点v之间有一条连边。保证这N-1条边会构成一棵树。

接下来M行，每行有2-3个数。第i行表示你需要完成的第i个操作是什么。

Output Format

对于每一个询问，依次输出相应的答案。

答案之间用换行符隔开。

Sample Input

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

Sample Output

3
3
0

Hint

对于30%的数据，N ≤ 10,000。

对于100%的数据，1 ≤ N, M ≤ 500,000。

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！