Dado un árbol N-ario con algún color asociado con cada Node y consultas Q. Cada consulta contiene dos enteros A y X . La tarea es contar todos los colores distintos en un subárbol con raíz en A , que tenga una frecuencia de colores mayor o igual a X en ese subárbol.
Ejemplos:
Entrada: Árbol:
1(1) / \ / \ 2(2) 5(3) / \ / | \ / \ / | \ 3(2) 4(3) 6(2) 7(3) 8(3)consulta[] = {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {5, 3}}
Salida: {2, 2, 1, 0, 1}
Explicación:
En el subárbol con raíz en 1, la frecuencia del color 2 es 3 y el color 3 es 4. Entonces, la respuesta es 2 para la consulta 1, 2 para la consulta 2 y 1 para la consulta 3.
Para el subárbol con raíz en 2, la frecuencia del color 2 es 2 y el color 3 es 1. Por lo tanto, ningún color tiene una frecuencia mayor o igual a 4.
Para el subárbol con raíz en 5, la frecuencia del color 2 es 1 y el color 3 es 3. Entonces, el color 3 tienen frecuencia igual a 3.
Enfoque ingenuo
- Para cada consulta, recorreremos todo el subárbol del Node dado.
- Mantendremos un mapa que almacene la frecuencia de cada color en el subárbol de un Node dado.
- Luego, recorra el mapa y cuente el número de colores tal que su frecuencia sea mayor que la x dada.
Complejidad de tiempo: O(Q * N)
Complejidad de espacio: O(Q * N)
Enfoque: (usando el algoritmo de Mo)
- Primero aplanaremos el árbol usando Euler Tour .
- Le daremos el número a cada Node, cuándo entrará en el DFS y cuándo saldrá. Denotemos esto con tin[node] y tout[node] para cada Node.
- Después de aplanar el árbol en una array , cada subárbol de puede denotarse como una array con índice de inicio y final como tin[Node] y tout[Node] respectivamente.
- Ahora la pregunta cambió a número de elementos con frecuencia mayor que igual a X en algún subarreglo.
- Usaremos el algoritmo de Mo para resolver este problema.
- Primero, almacenaremos las consultas y las ordenaremos según tin[node] / SQ donde SQ es la raíz cuadrada de N .
- A medida que movemos los punteros, almacenaremos la frecuencia en el i-ésimo color en una array y la respuesta a la consulta se almacenará en la X -ésima posición de la array, ya que almacena el recuento de colores con una frecuencia mayor que X.
CPP
// C++ program to count distinct colors
// in a subtree of a Colored Tree
// with given min frequency for Q queries
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
// graph as adjacency list
vector<vector<int> > v(N);
// colour written on node.
vector<int> colour(N);
// order of node entering in DFS
vector<int> in(N);
// order of node exiting in DFS
vector<int> out(N);
// for counting the frequency of
// nodes with colour i
vector<int> cnt(N);
// for storing frequency of colours
vector<int> freq(N);
// tree in a flatten
// form (using Euler tour)
vector<int> flatTree(N);
// number of nodes
int n,
// square root of n
sq;
// indexes for in and
// out of node in DFS
int start = 0;
// DFS function to find
// order of euler tour
void DFSEuler(int a, int par)
{
// storing the start index
in[a] = ++start;
// storing colour of node
// in flatten array
flatTree[start] = colour[a];
for (int i : v[a]) {
// doing DFS on its child
// skipping parent
if (i == par)
continue;
DFSEuler(i, a);
}
// out index of the node.
out[a] = start;
}
// comparator for queries
bool comparator(pair<int, int>& a,
pair<int, int>& b)
{
// comparator for queries to be
// sorted according to in[x] / sq
if (in[a.first] / sq != in[b.first] / sq)
return in[a.first] < in[b.first];
return out[a.first] < out[b.first];
}
// Function to answer the queries
void solve(vector<pair<int, int> > arr,
int q)
{
sq = sqrt(n) + 1;
// for storing answers
vector<int> answer(q);
// for storing indexes of queries
// in the order of input.
map<pair<int, int>, int> idx;
for (int i = 0; i < q; i++) {
// storing indexes of queries
idx[arr[i]] = i;
}
// doing depth first search to
// find indexes to flat the
// tree using euler tour.
DFSEuler(1, 0);
// After doing Euler tour,
// subtree of x can be
// represented as a subarray
// from in[x] to out[x];
// we'll sort the queries
// according to the in[i];
sort(arr.begin(),
arr.end(),
comparator);
// two pointers for
// sliding the window
int l = 1, r = 0;
for (int i = 0; i < q; i++) {
// finding answer to the query
int node = arr[i].first,
x = arr[i].second;
int id = idx[arr[i]];
while (l > in[node]) {
// decrementing the pointer as
// it is greater than start
// and adding answer
// to our freq array.
l--;
cnt[flatTree[l]]++;
freq[cnt[flatTree[l]]]++;
}
while (r < out[node]) {
// incrementing pointer as it is
// less than the end value and
// adding answer to our freq array.
r++;
cnt[flatTree[r]]++;
freq[cnt[flatTree[r]]]++;
}
while (l < in[node]) {
// removing the lth node from
// freq array and incrementing
// the pointer
freq[cnt[flatTree[l]]]--;
cnt[flatTree[l]]--;
l++;
}
while (r > out[node]) {
// removing the rth node from
// freq array and decrementing
// the pointer
freq[cnt[flatTree[r]]]--;
cnt[flatTree[r]]--;
r--;
}
// answer to this query
// is stored at freq[x]
// freq[x] stores the frequency
// of nodes greater equal to x
answer[id] = freq[x];
}
// printing the queries
for (int i = 0; i < q; i++)
cout << answer[i] << " ";
}
int main()
{
// Driver Code
/*
1(1)
/ \
/ \
2(2) 5(3)
/ \ / | \
/ \ / | \
3(2) 4(3) 6(2) 7(3) 8(3)
*/
n = 8;
v[1].push_back(2);
v[2].push_back(1);
v[2].push_back(3);
v[3].push_back(2);
v[2].push_back(4);
v[4].push_back(2);
v[1].push_back(5);
v[5].push_back(1);
v[5].push_back(6);
v[6].push_back(5);
v[5].push_back(7);
v[7].push_back(5);
v[5].push_back(8);
v[8].push_back(5);
colour[1] = 1;
colour[2] = 2;
colour[3] = 2;
colour[4] = 3;
colour[5] = 3;
colour[6] = 2;
colour[7] = 3;
colour[8] = 3;
vector<pair<int, int> > queries
= { { 1, 2 },
{ 1, 3 },
{ 1, 4 },
{ 2, 3 },
{ 5, 3 } };
int q = queries.size();
solve(queries, q);
return 0;
}
Producción:
2 2 1 0 1
Complejidad de tiempo: 
Complejidad de espacio: 
Publicación traducida automáticamente
Artículo escrito por insiderpants y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA