Dado un árbol N-ario con raíz en 1 , y una array val[] que consta de pesos asignados a cada Node, y una array Q[][] , que consta de consultas de la forma {X, D} , la tarea para cada consulta es encontrar el mínimo de todos los pesos asignados a los Nodes que están como máximo a una distancia D del Node X.
Ejemplos:
Entrada: Q[][] = {{1, 2}, {2, 1}}, val[] = {1, 2, 3, 3, 5}
1 / \ 4 5 / 3 / 2Salida:
1
3
Explicación:
Consulta 1: X = 1, D = 2
Los Nodes a una distancia máxima de 2 del Node 1 son {1, 3, 4, 5} y los pesos asignados a estos Nodes son {1, 3, 3, 5} respectivamente.
Por lo tanto, el peso mínimo asignado es 1.
Consulta 2: X = 2, D = 1
Los Nodes a una distancia máxima de 1 del Node 2 son {2, 3} y los pesos asignados a estos Nodes son {2, 3} respectivamente.
Por lo tanto, el peso mínimo asignado es 2.Entrada: Q[][] = {{1, 2}}, val[] = {1, 2, 4}
1 / \ 2 3Salida: 1
Enfoque ingenuo:
el enfoque más simple para resolver cada consulta es iterar el árbol y encontrar todos los Nodes que estén como máximo a una distancia D del Node X y encontrar el mínimo de todos los pesos asignados a estos Nodes.
Complejidad temporal: O(Q * N)
Espacio auxiliar: O(1)
Enfoque eficiente:
para optimizar el enfoque anterior, siga los pasos a continuación:
- Implemente el Euler Tour del árbol y asigne un índice a cada Node del árbol.
- Ahora, en cada índice, almacene la profundidad y el valor asociado con el Node en una array.
- Cree Merge Sort Tree en la array y ordene el rango de acuerdo con la profundidad de los Nodes.
- Para cada consulta, se sabe que todos los Nodes del subárbol de X se encuentran entre las arrays in[X] y out[X], donde in y out son el índice en el que los Nodes realizan DFS .
- En este rango, encuentre el Node ponderado mínimo que tenga una distancia de D como máximo . Cree el árbol de clasificación por combinación y combine los dos rangos de acuerdo con el orden creciente de profundidad y encuentre el prefijo mínimo entre los valores en cada Node del árbol de clasificación por combinación .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 9;
/// Function to perform DFs
void dfs(int a, int par, int dep,
vector<vector<int> >& v,
vector<int>& depth, vector<int>& in,
vector<int>& out,
vector<pair<int, int> >& inv,
vector<int>& val, int& tim)
{
// Assign depth
depth[a] = dep;
// Assign in-time
in[a] = ++tim;
// Store depth and value to
// construct Merge Sort Tree
inv[tim] = make_pair(depth[a], val[a]);
for (int i : v[a]) {
// Skip the parent
if (i == par)
continue;
dfs(i, a, dep + 1, v, depth, in,
out, inv, val, tim);
}
// Assign out-time
out[a] = tim;
}
// Function to build the Merge Sort Tree
void build(int node, int l, int r,
vector<vector<pair<int,
int> > >& segtree,
vector<pair<int, int> >& inv)
{
// If the current node is
// a leaf node
if (l == r) {
segtree[node].push_back(inv[l]);
return;
}
int mid = (l + r) >> 1;
// Recursively build left and right subtree
build(2 * node + 1, l, mid, segtree, inv);
build(2 * node + 2, mid + 1, r, segtree, inv);
// Merge left and right node
// of merge sort tree
merge(segtree[2 * node + 1].begin(),
segtree[2 * node + 1].end(),
segtree[2 * node + 2].begin(),
segtree[2 * node + 2].end(),
back_inserter(segtree[node]));
int mn = INF;
for (auto& i : segtree[node]) {
// Compute the prefix minimum
mn = min(mn, i.second);
i.second = mn;
}
}
// Function to solve each query
int query(int x, int y, int dep, int node,
int l, int r,
vector<vector<pair<int,
int> > >& segtree)
{
// Check for no overlap
if (l > y || r < x || x > y)
return INF;
// Condition for complete overlap
if (x <= l && r <= y) {
// Find the node with
// depth greater than d;
auto it
= upper_bound(segtree[node].begin(),
segtree[node].end(),
make_pair(dep, INF));
if (it == segtree[node].begin())
// Return if the first depth
// is greater than d
return INF;
// Decrement the pointer;
it--;
// Return prefix minimum
return it->second;
}
int mid = (l + r) >> 1;
int a = query(x, y, dep, 2 * node + 1,
l, mid, segtree);
int b = query(x, y, dep, 2 * node + 2,
mid + 1, r, segtree);
return min(a, b);
}
// Function to compute the queries
void answerQueries(vector<pair<int, int> > queries,
vector<vector<int> >& v,
vector<int> val, int n)
{
// Stores the time
int tim = 0;
// Stores the in and out time
vector<int> in(n + 10), out(n + 10);
// Stores depth
vector<int> depth(n + 10);
vector<pair<int, int> > inv(n + 10);
dfs(1, 0, 0, v, depth, in, out, inv, val, tim);
// Merge sort tree to store
// depth of each node
vector<vector<pair<int,
int> > >
segtree(4 * n + 10);
// Construct the merge sort tree
build(0, 1, tim, segtree, inv);
for (auto& i : queries) {
int x = i.first;
int dep = depth[x] + i.second;
// Find the minimum value in subtree of x
// and subtree of x lies from in[x]
// to out[x] in merge sort tree
int minVal = query(in[x], out[x], dep, 0,
1, tim, segtree);
cout << minVal << endl;
}
}
// Driver Code
int main()
{
/*
1
/ \
4 5
/
3
/
2
*/
int n = 5;
// Stores the graph
vector<vector<int> > v(n + 1);
// Stores the weights
vector<int> val(n + 1);
// Assign edges
v[1].push_back(4);
v[4].push_back(1);
v[1].push_back(5);
v[5].push_back(1);
v[4].push_back(3);
v[3].push_back(4);
v[3].push_back(2);
v[2].push_back(3);
// Assign weights
val[1] = 1;
val[2] = 3;
val[3] = 2;
val[4] = 3;
val[5] = 5;
// Stores the queries
vector<pair<int, int> > queries = { { 1, 2 },
{ 2, 1 } };
answerQueries(queries, v, val, n);
return 0;
}
1 3
Complejidad de tiempo: O(N * log(N) + Q * log(N))
Espacio auxiliar: O(N * log N)
Publicación traducida automáticamente
Artículo escrito por insiderpants y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA