Skip to content

11298: 【原1298】柏爷神树

题目

题目描述

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

Description

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

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

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

  • \(1 x value\) 表示将节点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了,可以的话,请您参考添加页面,与大家一起分享你的题解!