Solução Informática Avançado - Semana 56

Por Samyra Almeida

Para resolver esse problema é necessário conhecimento sobre a estrutura da segmente tree com lazy propagation e saber linearizar uma árvore usando os tempos de entrada e saída da DFS.

Vamos definir o nível de um nó o número de arestas no caminho da raiz para o nó. Raiz (nó 1) está no nível 1, os filhos da raiz estão no nível 2, os filhos dos filhos da raiz estão no nível 3 e assim por diante.

Agora, suponha que você queira fazer uma operação do tipo 1 para um nó $x$ . Quais nós da subárvore de $x$ serão adicionados $+val$ (um valor positivo)? Obviamente, $x$ será o primeiro, sendo localizado no nível $H$ . Filhos de $x$ , localizado no nível $H + 1$ , será adicionado $-val$ . Filhos de filhos, localizados no nível $H + 2$ , serão adicionados valor + val novamente. Assim, os nós da subárvore de $x$ localizados nos níveis $H, H + 2, H + 4,$ $...$ serão adicionados a $+val$ e os nós localizados nos níveis $H + 1, H + 3, H + 5,$ $...$ serão adicionados $-val$ . Note que para um $x$ fixo, em um nível $H$ , e y um nó da subárvore de $x$ , no nível $H2$ . Se $H$ e $H2$ tiverem a mesma paridade, $+val$ será adicionado a $y$ . Caso contrário, $-val$ será adicionado a $y$ .

A partir daqui, temos a ideia de dividir os nós da árvore em dois conjuntos - os que estão localizados no nível par e os que estão localizados no nível ímpar. O que ainda torna o problema difícil de resolver? O fato de termos uma árvore. Se os nós de uma subárvore fossem uma sequência contígua em vez de alguns nós de uma árvore, o problema seria mais simples: o problema reduziria para adicionar/subtrair valores a todos os elementos de um subarray e consultar um valor atual de um elemento de matriz. Então, como podemos transformar árvore em um array, como para um nó $x$ , todos os nós da subárvore de $x$ para ser um subarray de array?

A resposta é sim. Podemos fazer isso utilizando as propriedades de busca na DFS. Antes de continuar lendo, verifique se você sabe o que é o tempo de descoberta e o horário de término em uma busca na DFS. Vamos construir 3 arrays agora - $descoberta[]$ , representando nós na ordem de seus tempos de descoberta, $entrada[]$ $=$ para um nó, tempo em que foi descoberto e $saida[]$ $=$ qual é a última vez que um nó da de sua subárvore foi descoberto antes que esse nó seja concluído. Para uma subárvore de $x$ , todos os nós na subárvore são nós em descoberta estão entre as posições de $entrada[x]$ a $saida[x]$ .

Exemplo: suponha que você tenha árvore $1$ $-$ $5;$ $1$ $-$ $6;$ $6$ $-$ $7;$ $6$ $-$ $4;$ $4$ $-$ $2;$ $4$ $-$ $3$ .

$descoberta$ é { $1, 5, 6, 7, 4, 2, 3$ }.
$entrada$ é { $1, 6, 7, 5, 2, 3, 4$ }.
$saida$ é { $7, 6, 7, 7, 2, 7, 4$ }.

Qual é a subárvore do nó 6? elementos de descoberta da posição $entrada[6]$ ao $saida[6]$ . Neste caso, de $3$ a $7$ , os elementos ${6, 7, 4, 2, 3}$ .

Agora, reduzimos o problema para: você recebe um vetor $A$ . você pode executar duas operações:

$1$ $-$ aumenta todos os elementos de um intervalo $[x,$ $y]$ para um valor $val$ ( $val$ pode ser negativo, para tratar subtrações)
$2$ $-$ consulta o valor atual de um elemento da posição $pos$ .

Podemos realizar essas operações utilizando a estrutura da segment tree com lazy propagation, se você não conhece essa estrutura, leia sobre elas antes de prosseguir.

Iremos criar duas segment tree de soma uma para os nós de nível par e outra para os de nível ímpar. Na função $update$ atualizamos um intervalo $[x$ , $y]$ iremos realizar a atualização nas duas segs e nas duas lazys simultanealmente, definindo $+val$ para a seg ímpar e $-val$ para a par, e ao consultar o valor de um nó ao chegar em uma folha da seg, basta checarmos a paridade do nível do nó e então retornamos seu o valor em sua respectiva seg.

Para maior compreensão leia atentamente o código solução abaixo:

	#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[4maxn], segp[4maxn];
	int lazyi[4maxn], lazyp[4maxn];

	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 = 2u, d = 2u + 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 = 2u, d = 2u + 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 = 2u, d = 2u + 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 = 2u, d = 2u + 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;
	}

view raw

noic-solucao-avancado-s56.cpp

hosted with ❤ by GitHub