noic-solucao-avancado-s56.cpp

#include <bits/stdc++.h>

using namespace std;

const int maxn=2e5+10;

// declaro as variáveis que vou utilizar
int n, m, t, num[maxn];
int h[maxn], descoberta[maxn];
int entrada[maxn], saida[maxn];
int segi[4*maxn], segp[4*maxn];
int lazyi[4*maxn], lazyp[4*maxn];

vector<int> graph[maxn];

void dfs(int u, int f) // linearizo a árvore
{
	descoberta[++t] = u; // adiciono u ao vetor da árvore linearizada
	entrada[u] = saida[u] = t; // salvo os tempos de inicio e saída de u
	h[u] = h[f] + 1; // salvo a altura d e u
	
	for(auto v: graph[u]) // percorro os filhos de u
	{
		if(v==f) continue;

		dfs(v, u);
		
		saida[u] = max(saida[u], saida[v]); // atualizo o tempo de saída
	}
}

void build(int u, int l, int r)
{
	if(l == r) // se estou em uma folha da seg
	{
		if(h[descoberta[l]]%2 == 1) segi[u] = num[descoberta[l]]; // se estou em um nó de nivel ímpar adiciono em segi
		else segp[u] = num[descoberta[l]]; // se for um nó de nível par adiociono em segp

		return;
	}

	int mid=(l+r)/2, e = 2*u, d = 2*u + 1;	
	
	build(e, l, mid);
	build(d, mid+1, r);

	// atualizo as duas segs
	segi[u] = segi[e] + segi[d]; 
	segp[u] = segp[e] + segp[d];
}

void lazyup(int u, int l, int r) // refresh na lazy
{
	int e = 2*u, d = 2*u + 1;

	if(lazyi[u] != 0) // se a lazyi for diferente de 0 atulizado ela e propago seu valor para os filhos
	{
		if(l != r)
		{
			lazyi[e]+=lazyi[u];
			lazyi[d]+=lazyi[u];
		}

		segi[u] += lazyi[u]*(r - l + 1);
		lazyi[u] = 0;
	}
	if(lazyp[u] != 0) // se a lazyp for diferente de 0 atulizado ela e propago seu valor para os filhos
	{
		if(l != r)
		{
			lazyp[e] += lazyp[u];
			lazyp[d] += lazyp[u];
		}

		segp[u] += lazyp[u]*(r - l + 1);
		lazyp[u] = 0;
	}
}

void upd(int u, int l, int r, int a, int b, int val)
{
	lazyup(u, l, r); // propago e atualizo a lazy de u

	if(l > b || r < a) return; // se estou em um intervalo invalido, retorno

	if(a <= l && r <= b){ // se estou em um intervalo totalmente valido
		
		// atualizo as lazys
		lazyi[u] += val;
		lazyp[u] -= val;

		lazyup(u, l, r); // propago e atualizo a lazy de u

		return;
	}

	int mid=(l+r)/2, e = 2*u, d = 2*u + 1;

	upd(e, l, mid, a, b, val); 
	upd(d, mid+1, r, a, b, val);

	// atualizo as segs
	segi[u] = segi[e] + segi[d];
	segp[u] = segp[e] + segp[d];	
}

int get(int u, int l, int r, int i)
{
	lazyup(u, l, r); // propago e atualizo a lazy de u

	if(l == r) // se estou em uma folha
	{
		// retorno o valor da respectiva seg
		if(h[descoberta[l]]%2 == 1) return segi[u];
		else return segp[u];
	}

	int mid = (l+r)/2, e = 2*u, d = 2*u + 1;

	if(i <= mid) return get(e, l, mid, i);
	else return get(d, mid+1, r, i);
}


int main(){
	
	scanf("%d%d", &n, &m);

	for(int i = 1 ; i <= n ; ++i) // leio os valores dos nós
		scanf("%d", &num[i]);

	for(int i = 1 ; i < n ; ++i) // monto a árvore
	{
		int u, v;
		scanf("%d%d", &u, &v);

		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	dfs(1, 1); // linerializo a árvore
	build(1, 1, t); // inicio os valores nas segs

	for(int i = 0 ; i < m ; ++i) // faço as operações
	{
		int id, x;
		scanf("%d %d", &id, &x);

		if(id == 1){
		
			int val;
			scanf("%d", &val);
		
			if(h[x]%2 == 0) val =- val; // se eu estou em um nó do nível par, troco o sinal de val

			upd(1, 1, t, entrada[x], saida[x], val); // atualizo as segs
		}
		else printf("%d\n", get(1, 1, t, entrada[x])); // imprimo o valor do nó x
	}

	return 0;
}