Se le da un árbol n-ario con una propiedad especial :
si rompemos un Node aleatorio del árbol, este Node junto con sus padres inmediatos hasta la raíz se desvanece. El árbol tiene N Nodes y los Nodes están numerados del 1 al N. La raíz siempre está en 1. Dada una secuencia de consultas que indica el número del Node que comenzamos a explotar, el problema es encontrar el número de subárboles que se formarían en el final de acuerdo con la propiedad anterior, para cada consulta de forma independiente.
Ejemplos:
Input:
Consider the following tree:
1
/ | \
2 3 4
/ \ \
5 6 7
/ \
8 9
q = 2
n = 1
n = 7
Output:
3
4
Explanation:
In the first query after bursting node 1, there
will be 3 subtrees formed rooted at 2, 3 and 4.
In the second query after bursting node 7, nodes
4 and 1 also get burst, thus there will
be 4 subtrees formed rooted at 8, 9, 2 and 3.
Como estamos tratando con un árbol n-ario, podemos usar una representación similar a la de un gráfico y agregar los bordes bidireccionales en una array de listas. Ahora, si rompemos un Node, podemos decir con seguridad que todos sus hijos se convertirán en subárboles separados. Además, todos los hijos de sus padres y otros antepasados hasta la raíz que estalló, también se convertirán en subárboles separados. Entonces, en nuestra respuesta final, queremos excluir el Node actual y todos sus ancestros en el camino hasta la raíz. Así podemos formar la ecuación a resolver como:
respuesta[Node] = grado[Node] + allChild[padre[Node]] – countPath[Node]
where allChild[]: número de hijos del Node + número de hijos de su
padre + ..+ número de hijos de la raíz
padre[]: padre de un Node en el árbol
grado[]: número de hijos para un Node
rutacuenta[]: número de Nodes desde la raíz hasta el padre del Node
Podemos llenar todas las arrays anteriores utilizando la búsqueda en profundidad primero en la lista de adyacencia. Podemos comenzar desde la raíz 1, asumiendo que su padre es 0 y repetir la profundidad primero para propagar sus valores a sus hijos. Por lo tanto, podemos preprocesar y llenar las arrays anteriores inicialmente y devolver el valor de la ecuación para cada consulta en consecuencia.
La siguiente es la implementación del enfoque anterior:
C++
// C++ program to find number of subtrees after bursting nodes
#include <bits/stdc++.h>
using namespace std;
// do depth first search of node nod; par is its parent
void dfs(int nod, int par, list<int> adj[], int allChild[],
int parent[], int degree[], int countPath[])
{
// go through the adjacent nodes
for (auto it = adj[nod].begin(); it != adj[nod].end(); it++) {
int curr = *it;
// avoid cycling
if (curr == par)
continue;
degree[nod]++;
countPath[curr] = countPath[nod] + 1;
parent[curr] = nod;
}
// propagated from parent
allChild[nod] = allChild[parent[nod]] + degree[nod];
// go through the adjacent nodes
for (auto it = adj[nod].begin(); it != adj[nod].end(); it++) {
int curr = *it;
// avoid cycling
if (curr == par)
continue;
// recur and go depth first
dfs(curr, nod, adj, allChild, parent, degree, countPath);
}
}
// Driver code
int main()
{
int n = 9;
// adjacency list for each node
list<int> adj[n + 1];
// allChild[]: number of node's children + number of its
// parent's children + ..+ number of root's children
// parent[]: parent of a node in the tree
// degree[]: number of children for a node
// countPath[]: number of nodes from root to parent of node
int allChild[n + 1] = { 0 }, parent[n + 1] = { 0 },
degree[n + 1] = { 0 }, countPath[n + 1] = { 0 };
// construct tree
adj[1].push_back(2);
adj[2].push_back(1);
adj[1].push_back(3);
adj[3].push_back(1);
adj[1].push_back(4);
adj[4].push_back(1);
adj[3].push_back(5);
adj[5].push_back(3);
adj[3].push_back(6);
adj[6].push_back(3);
adj[4].push_back(7);
adj[7].push_back(4);
adj[7].push_back(8);
adj[8].push_back(7);
adj[7].push_back(9);
adj[9].push_back(7);
// assume 1 is root and 0 is its parent
dfs(1, 0, adj, allChild, parent, degree, countPath);
// 2 queries
int curr = 1;
cout << degree[curr] + allChild[parent[curr]] - countPath[curr] << endl;
curr = 7;
cout << degree[curr] + allChild[parent[curr]] - countPath[curr] << endl;
return 0;
}
Java
// Java program to find number of subtrees
// after bursting nodes
import java.util.*;
class GFG{
// Do depth first search of node nod;
// par is its parent
static void dfs(int nod, int par,
List<Integer> adj[],
int allChild[],
int parent[],
int degree[],
int countPath[])
{
// Go through the adjacent nodes
for(int it : adj[nod])
{
int curr = it;
// astatic void cycling
if (curr == par)
continue;
degree[nod]++;
countPath[curr] = countPath[nod] + 1;
parent[curr] = nod;
}
// Propagated from parent
allChild[nod] = allChild[parent[nod]] +
degree[nod];
// Go through the adjacent nodes
for(int it : adj[nod])
{
int curr = it;
// astatic void cycling
if (curr == par)
continue;
// recur and go depth first
dfs(curr, nod, adj, allChild,
parent, degree, countPath);
}
}
// Driver code
public static void main(String[] args)
{
int n = 9;
// Adjacency list for each node
@SuppressWarnings("unchecked")
List<Integer> []adj = new List[n + 1];
for(int i = 0; i < adj.length; i++)
adj[i] = new Vector<Integer>();
// allChild[]: number of node's children +
// number of its parent's children + ..+
// number of root's children
// parent[]: parent of a node in the tree
// degree[]: number of children for a node
// countPath[]: number of nodes from root
// to parent of node
int []allChild = new int[n + 1];
int []parent = new int[n + 1];
int []degree = new int[n + 1];
int []countPath = new int[n + 1];
// Contree
adj[1].add(2);
adj[2].add(1);
adj[1].add(3);
adj[3].add(1);
adj[1].add(4);
adj[4].add(1);
adj[3].add(5);
adj[5].add(3);
adj[3].add(6);
adj[6].add(3);
adj[4].add(7);
adj[7].add(4);
adj[7].add(8);
adj[8].add(7);
adj[7].add(9);
adj[9].add(7);
// Assume 1 is root and 0 is its parent
dfs(1, 0, adj, allChild, parent,
degree, countPath);
// 2 queries
int curr = 1;
System.out.print(degree[curr] +
allChild[parent[curr]] -
countPath[curr] + "\n");
curr = 7;
System.out.print(degree[curr] +
allChild[parent[curr]] -
countPath[curr] + "\n");
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program to find number of # subtrees after bursting nodes # Do depth first search of node # nod par is its parent def dfs(nod, par, adj, allChild, parent, degree, countPath): # Go through the adjacent nodes for it in adj[nod]: curr = it # Avoid cycling if (curr == par): continue degree[nod] += 1 countPath[curr] = countPath[nod] + 1 parent[curr] = nod # Propagated from parent allChild[nod] = (allChild[parent[nod]] + degree[nod]) # Go through the adjacent nodes for it in adj[nod]: curr = it # Avoid cycling if (curr == par): continue # recur and go depth first dfs(curr, nod, adj, allChild, parent, degree, countPath) # Driver code if __name__ == '__main__': n = 9 # Adjacency list for each node adj = [[] for i in range(n + 1)] # allChild: number of node's children + number of its # parent's children + ..+ number of root's children # parent: parent of a node in the tree # degree: number of children for a node # countPath: number of nodes from root to parent of node allChild, parent = [0] * (n + 1), [0] * (n + 1) degree, countPath = [0] * (n + 1), [0] * (n + 1) # Construct tree adj[1].append(2) adj[2].append(1) adj[1].append(3) adj[3].append(1) adj[1].append(4) adj[4].append(1) adj[3].append(5) adj[5].append(3) adj[3].append(6) adj[6].append(3) adj[4].append(7) adj[7].append(4) adj[7].append(8) adj[8].append(7) adj[7].append(9) adj[9].append(7) # Assume 1 is root and 0 is its parent dfs(1, 0, adj, allChild, parent, degree, countPath) # 2 queries curr = 1 print(degree[curr] + allChild[parent[curr]] - countPath[curr]) curr = 7 print(degree[curr] + allChild[parent[curr]] - countPath[curr]) # This code is contributed by mohit kumar 29
C#
// C# program to find number of subtrees
// after bursting nodes
using System;
using System.Collections.Generic;
class GFG{
// Do depth first search of node nod;
// par is its parent
static void dfs(int nod, int par,
List<int> []adj,
int []allChild,
int []parent,
int []degree,
int []countPath)
{
// Go through the adjacent nodes
foreach(int it in adj[nod])
{
int curr = it;
// astatic void cycling
if (curr == par)
continue;
degree[nod]++;
countPath[curr] = countPath[nod] + 1;
parent[curr] = nod;
}
// Propagated from parent
allChild[nod] = allChild[parent[nod]] +
degree[nod];
// Go through the adjacent nodes
foreach(int it in adj[nod])
{
int curr = it;
// astatic void cycling
if (curr == par)
continue;
// recur and go depth first
dfs(curr, nod, adj, allChild,
parent, degree, countPath);
}
}
// Driver code
public static void Main(String[] args)
{
int n = 9;
// Adjacency list for each node
List<int> []adj = new List<int>[n + 1];
for(int i = 0; i < adj.Length; i++)
adj[i] = new List<int>();
// allChild[]: number of node's children +
// number of its parent's children + ..+
// number of root's children
// parent[]: parent of a node in the tree
// degree[]: number of children for a node
// countPath[]: number of nodes from root
// to parent of node
int []allChild = new int[n + 1];
int []parent = new int[n + 1];
int []degree = new int[n + 1];
int []countPath = new int[n + 1];
// Contree
adj[1].Add(2);
adj[2].Add(1);
adj[1].Add(3);
adj[3].Add(1);
adj[1].Add(4);
adj[4].Add(1);
adj[3].Add(5);
adj[5].Add(3);
adj[3].Add(6);
adj[6].Add(3);
adj[4].Add(7);
adj[7].Add(4);
adj[7].Add(8);
adj[8].Add(7);
adj[7].Add(9);
adj[9].Add(7);
// Assume 1 is root and 0 is its parent
dfs(1, 0, adj, allChild, parent,
degree, countPath);
// 2 queries
int curr = 1;
Console.Write(degree[curr] +
allChild[parent[curr]] -
countPath[curr] + "\n");
curr = 7;
Console.Write(degree[curr] +
allChild[parent[curr]] -
countPath[curr] + "\n");
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program to find number of subtrees
// after bursting nodes
// Do depth first search of node nod;
// par is its parent
function dfs(nod,par,adj,allChild,parent,degree,countPath)
{
// Go through the adjacent nodes
for(let it=0;it<adj[nod].length;it++)
{
let curr = adj[nod][it];
// astatic void cycling
if (curr == par)
continue;
degree[nod]++;
countPath[curr] = countPath[nod] + 1;
parent[curr] = nod;
}
// Propagated from parent
allChild[nod] = allChild[parent[nod]] +
degree[nod];
// Go through the adjacent nodes
for(let it=0;it<adj[nod].length;it++)
{
let curr = adj[nod][it];
// astatic void cycling
if (curr == par)
continue;
// recur and go depth first
dfs(curr, nod, adj, allChild,
parent, degree, countPath);
}
}
// Driver code
let n = 9;
// Adjacency list for each node
let adj = new Array(n + 1);
for(let i = 0; i < adj.length; i++)
adj[i] = [];
// allChild[]: number of node's children +
// number of its parent's children + ..+
// number of root's children
// parent[]: parent of a node in the tree
// degree[]: number of children for a node
// countPath[]: number of nodes from root
// to parent of node
let allChild = new Array(n + 1);
let parent = new Array(n + 1);
let degree = new Array(n + 1);
let countPath = new Array(n + 1);
for(let i=0;i<n+1;i++)
{
allChild[i]=0;
parent[i]=0;
degree[i]=0;
countPath[i]=0;
}
// Contree
adj[1].push(2);
adj[2].push(1);
adj[1].push(3);
adj[3].push(1);
adj[1].push(4);
adj[4].push(1);
adj[3].push(5);
adj[5].push(3);
adj[3].push(6);
adj[6].push(3);
adj[4].push(7);
adj[7].push(4);
adj[7].push(8);
adj[8].push(7);
adj[7].push(9);
adj[9].push(7);
// Assume 1 is root and 0 is its parent
dfs(1, 0, adj, allChild, parent,
degree, countPath);
// 2 queries
let curr = 1;
document.write(degree[curr] +
allChild[parent[curr]] -
countPath[curr] + "<br>");
curr = 7;
document.write(degree[curr] +
allChild[parent[curr]] -
countPath[curr] + "<br>");
// This code is contributed by unknown2108
</script>
Producción
3 4
La complejidad temporal del algoritmo anterior es O(E * lg(V)) donde E id es el número de aristas y V es el número de vértices.
Publicación traducida automáticamente
Artículo escrito por rsatish1110 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA