Original title link: Problem - 383C - Codeforces

The meaning of the topic:

  Give you a root node as The tree of , each point has a point weight, you have to complete the following operations:

- Operation 1: send to nodeadd a value.

- Operation 2: Ask the nodepoint right.

  This tree also has a magical property: when youadd a valueWhen , nodeThe child nodes of will be added with, the child nodes of the child nodes will be added, and so on until the bottom of the tree.

Problem-solving ideas:

Seeing the interval operation on the child nodes of the tree, first think of the line segment tree. To maintain the information on the tree, you can use the tree section or dfs order to build the tree, and then maintain the weight of each node. But it is observed that this question is not as simple as adding intervals or subtracting intervals.

In the topic, add a value to each node, and add the opposite number of the value to its child nodes. We can draw a graph to observe the law.

For example, add a value to the root of the current tree, then the impact on this tree is as follows:

(red for plus, blue for minus)

        

We first consider the depth , relative to the root node, each time the depth increases, thenThe value of will become. Converted into easy-to-handle information, that is: points with the same odd/even depth as the root node are added, for even/odd depth points are added. The root node is added here, and the same applies to other points.

So can we try to use this property to maintain lazy markup? Yes, but with a change.

try root node as standard (depth of), the point with the same odd depth as the root node is fixed as the added value, while points at even depths are fixed to the plus value, so that every addition and subtraction is fixed, as shown in the figure below:

Even so, for odd points, lazy marks can be maintained, and we can get the correct answer, but what about even points?

Considering the fixed addition and subtraction, then when we add the value to the even points (blue points) in the figureWhen , we follow the fixed addition and subtraction just now, it will become an added value.

Then we can put the valuebecomes  ? Then for the fixed subtraction of even points, we will subtract one, that is, addingAlready!

Thinking of this step, this question came out. Using fixed addition and subtraction, if the current number is odd, update to the interval (). If there is an even number, update().

The code and specific explanation are as follows:

AC code:

#include <bits/stdc++.h>
#define lson k << 1, l, mid
#define rson k << 1 | 1, mid + 1, r
using namespace std;

using i64 = long long;
const int N = 2e5 + 10;

vector<int> g[N];//vector save image
//in out is the starting point and end point of the dfs sequence, id is the backtracking subscript when building a tree, and idx maintains the dfs sequence
int in[N], out[N], d[N], id[N], idx;

i64 seg[N << 2], dep[N << 2], lazy[N << 2];
//seg is line segment tree dep is tree depth lazy is lazy tag
int arr[N];

inline void dfn(int u, int fa)//run dfs sequence
{
	d[u] = d[fa] + 1, id[++idx] = u, in[u] = idx;
	for (auto& x : g[u])
		if (x != fa) dfn(x, u);
	out[u] = idx;
}

inline void pushdown(int k, int l, int r)
{
	//lt is the left son rt is the right son
	int mid = l + r >> 1, lt = k << 1, rt = k << 1 | 1;

	if (dep[lt] & 1) seg[lt] += lazy[k];//odd fixed plus
	else seg[lt] -= lazy[k];//even fixed minus

	if (dep[rt] & 1) seg[rt] += lazy[k];//odd fixed plus
	else seg[rt] -= lazy[k];//even fixed minus

 lazy[lt] += lazy[k], lazy[rt] += lazy[k], lazy[k] = 0;
}

inline void build(int k, int l, int r)//achievements
{
	if (l == r)
	{
		seg[k] = arr[id[l]];
		dep[k] = d[id[l]];
		return;
	}
	int mid = l + r >> 1;
	build(lson), build(rson);
}

inline void upd(int k, int l, int r, int x, int y, int z)//renew
{
	if (l >= x && r <= y) {
		lazy[k] += z;
		if (dep[k] & 1) seg[k] += z;//odd fixed plus
		else seg[k] -= z;//even fixed minus
		return;
	}
	if (lazy[k]) pushdown(k, l, r);
	int mid = l + r >> 1;
	if (x <= mid) upd(lson, x, y, z);
	if (y > mid) upd(rson, x, y, z);
}

inline i64 qry(int k, int l, int r, int x, int y)
{
	if (l >= x && r <= y) return seg[k];
	if (lazy[k]) pushdown(k, l, r);
	int mid = l + r >> 1;
	if (x <= mid) return qry(lson, x, y);
	if (y > mid) return qry(rson, x, y);
}

void solve()
{
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) cin >> arr[i];
	for (int i = 1, x, y; i <= n - 1; ++i)
	{
		cin >> x >> y;
		g[x].emplace_back(y);
		g[y].emplace_back(x);
	}

	dfn(1, 0);
	build(1, 1, n);

	for (int i = 0, x; i < q; ++i)
	{
		i64 z;
		cin >> x;
		if (x == 1)
		{
			cin >> x >> z;
			if (d[x] & 1) upd(1, 1, n, in[x], out[x], z);//odd plus z
			else upd(1, 1, n, in[x], out[x], -z);//Even numbers add -z
		}
		else
		{
			cin >> x;
			cout << qry(1, 1, n, in[x], in[x]) << '\n';
		}
	}
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int t = 1; //cin >> t;
	while (t--) solve();

	return 0;
}