Dado un árbol enraizado T, con ‘n’ Nodes, cada Node tiene un color indicado por la array color[](color[i] denota el color del i-ésimo Node en forma de número entero). Responder a las consultas ‘Q’ del siguiente tipo:
- distintiva u – Imprime el número de Nodes de distintos colores bajo el subárbol enraizado bajo ‘u’
Ejemplos:
1
/ \
2 3
/|\ | \
4 5 6 7 8
/| \
9 10 11
color[] = {0, 2, 3, 3, 4, 1, 3, 4, 3, 2, 1, 1}
Indexes NA 1 2 3 4 5 6 7 8 9 10 11
(Node Values and colors start from index 1)
distinct 3 -> output should be '4'.
There are six different nodes in the subtree rooted with
3, nodes are 3, 7, 8, 9, 10 and 11. These nodes have
four distinct colors (3, 4, 2 and 1)
distinct 2 -> output should be '3'.
distinct 7 -> output should be '3'.
Construyendo una solución en pasos:
- Aplane el árbol usando DFS; almacena la hora de visita y la hora de finalización de cada Node en dos arrays, vis_time[i] almacena la hora de visita del i-ésimo Node mientras que end_time[i] almacena la hora de finalización.
- En la misma llamada DFS, almacene el valor de color de cada Node en una array flat_tree[] , en los índices: vis_time[i] y end_time[i] para i-ésimo Node.
Nota: el tamaño de la array flat_tree[] será 2n.
Ahora el problema se reduce a encontrar el número de elementos distintos en el rango [vis_time[u], end_time[u] ] en la array flat_tree[] para cada consulta del tipo especificado. Para hacerlo, procesaremos las consultas fuera de línea (procesando las consultas en un orden diferente al proporcionado en la pregunta y almacenando los resultados, y finalmente imprimiendo el resultado de cada una en el orden especificado en la pregunta).
Pasos:
- Primero, procesamos previamente la array flat_tree[] ; mantenemos una tabla[] (una array de vectores), la tabla[i] almacena el vector que contiene todos los índices en flat_tree[] que tienen el valor i. Es decir, si flat_tree[j] = i , table[i] tendrá uno de sus elementos j .
- En BIT, actualizamos ‘1’ en el i-ésimo índice si queremos que el i-ésimo elemento de flat_tree[] se cuente en el método query() . Ahora mantenemos otro array traverser[] ; traverser[i] contiene el puntero al siguiente elemento de la tabla[i] que aún no está marcado en BIT.
- Ahora actualizamos nuestro BIT y establecemos ‘1’ en la primera aparición de cada elemento en flat_tree[] e incrementamos el correspondiente traverser[] en ‘1’ (si flat_tree[i] está ocurriendo por primera vez entonces traverser[flat_tree[i]] se incrementa en ‘1’) para apuntar a la siguiente aparición de ese elemento.
- Ahora nuestra función query(R) para BIT devolvería el número de elementos distintos en flat_tree[] en el rango [1, R] .
- Clasificamos todas las consultas en orden creciente vis_time[] , dejemos que l denote vis_time[ i ] y r i denote end_time[i] . Ordenar las consultas en orden creciente de l i nos da una ventaja, ya que al procesar la i-ésima consulta no veremos ninguna consulta en el futuro con su ‘ l ‘ menor que l i . Entonces, podemos eliminar todas las ocurrencias de los elementos hasta li – 1 de BIT y agregar sus próximas ocurrencias usando la array traverser[] . Y luego query(R) devolvería el número de elementos distintos en el rango[l yo , r yo ] .
C++
// A C++ program implementing the above design
#include<bits/stdc++.h>
#define max_color 1000005
#define maxn 100005
using namespace std;
// Note: All elements of global arrays are
// initially zero
// All the arrays have been described above
int bit[maxn], vis_time[maxn], end_time[maxn];
int flat_tree[2 * maxn];
vector<int> tree[maxn];
vector<int> table[max_color];
int traverser[max_color];
bool vis[maxn];
int tim = 0;
//li, ri and index are stored in queries vector
//in that order, as the sort function will use
//the value li for comparison
vector< pair< pair<int, int>, int> > queries;
//ans[i] stores answer to ith query
int ans[maxn];
//update function to add val to idx in BIT
void update(int idx, int val)
{
while ( idx < maxn )
{
bit[idx] += val;
idx += idx & -idx;
}
}
//query function to find sum(1, idx) in BIT
int query(int idx)
{
int res = 0;
while ( idx > 0 )
{
res += bit[idx];
idx -= idx & -idx;
}
return res;
}
void dfs(int v, int color[])
{
//mark the node visited
vis[v] = 1;
//set visiting time of the node v
vis_time[v] = ++tim;
//use the color of node v to fill flat_tree[]
flat_tree[tim] = color[v];
vector<int>::iterator it;
for (it=tree[v].begin(); it!=tree[v].end(); it++)
if (!vis[*it])
dfs(*it, color);
// set ending time for node v
end_time[v] = ++tim;
// setting its color in flat_tree[] again
flat_tree[tim] = color[v];
}
//function to add an edge(u, v) to the tree
void addEdge(int u, int v)
{
tree[u].push_back(v);
tree[v].push_back(u);
}
//function to build the table[] and also add
//first occurrences of elements to the BIT
void hashMarkFirstOccurrences(int n)
{
for (int i = 1 ; i <= 2 * n ; i++)
{
table[flat_tree[i]].push_back(i);
//if it is the first occurrence of the element
//then add it to the BIT and increment traverser
if (table[flat_tree[i]].size() == 1)
{
//add the occurrence to bit
update(i, 1);
//make traverser point to next occurrence
traverser[flat_tree[i]]++;
}
}
}
//function to process all the queries and store their answers
void processQueries()
{
int j = 1;
for (int i=0; i<queries.size(); i++)
{
//for each query remove all the occurrences before its li
//li is the visiting time of the node
//which is stored in first element of first pair
for ( ; j < queries[i].first.first ; j++ )
{
int elem = flat_tree[j];
//update(i, -1) removes an element at ith index
//in the BIT
update( table[elem][traverser[elem] - 1], -1);
//if there is another occurrence of the same element
if ( traverser[elem] < table[elem].size() )
{
//add the occurrence to the BIT and
//increment traverser
update(table[elem][ traverser[elem] ], 1);
traverser[elem]++;
}
}
//store the answer for the query, the index of the query
//is the second element of the pair
//And ri is stored in second element of the first pair
ans[queries[i].second] = query(queries[i].first.second);
}
}
// Count distinct colors in subtrees rooted with qVer[0],
// qVer[1], ...qVer[qn-1]
void countDistinctColors(int color[], int n, int qVer[], int qn)
{
// build the flat_tree[], vis_time[] and end_time[]
dfs(1, color);
// add query for u = 3, 2 and 7
for (int i=0; i<qn; i++)
queries.push_back(make_pair(make_pair(vis_time[qVer[i]],
end_time[qVer[i]]), i) );
// sort the queries in order of increasing vis_time
sort(queries.begin(), queries.end());
// make table[] and set '1' at first occurrences of elements
hashMarkFirstOccurrences(n);
// process queries
processQueries();
// print all the answers, in order asked
// in the question
for (int i=0; i<queries.size() ; i++)
{
cout << "Distinct colors in the corresponding subtree"
"is: " << ans[i] << endl;
}
}
//driver code
int main()
{
/*
1
/ \
2 3
/|\ | \
4 5 6 7 8
/| \
9 10 11 */
int n = 11;
int color[] = {0, 2, 3, 3, 4, 1, 3, 4, 3, 2, 1, 1};
// add all the edges to the tree
addEdge(1, 2);
addEdge(1, 3);
addEdge(2, 4);
addEdge(2, 5);
addEdge(2, 6);
addEdge(3, 7);
addEdge(3, 8);
addEdge(7, 9);
addEdge(7, 10);
addEdge(7, 11);
int qVer[] = {3, 2, 7};
int qn = sizeof(qVer)/sizeof(qVer[0]);
countDistinctColors(color, n, qVer, qn);
return 0;
}
Producción:
Distinct colors in the corresponding subtree is:4 Distinct colors in the corresponding subtree is:3 Distinct colors in the corresponding subtree is:3
Time Complexity: O( Q * log(n) )
Este artículo es una contribución de Saumye Malhotra . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA