Dado un árbol con N Nodes y un número K. Pinta cada Node del árbol en uno de los K colores disponibles.
Cuente y devuelva el número de formas de pintar el árbol de modo que dos Nodes cualesquiera que estén a una distancia de 1 o 2 se pinten de diferentes colores.
Ejemplos: La primera línea de la entrada contiene dos números enteros N y K.
La siguiente línea contiene una array de pares. Cada par (x, y) denota un borde no dirigido entre x e y.
Entrada : N = 3 K = 3
Árbol = { (2, 1), (3, 2) }
Salida: 6
Tenemos tres colores, digamos rojo, azul y verde. podemos pintar de las siguientes maneras.
Node 1 Node 2 Node 3 Rojo Azul Verde Rojo Verde Azul Azul Rojo Verde Azul Verde Rojo Verde Rojo Azul Verde Azul Rojo Por lo tanto, 6 es la respuesta.
Entrada: N = 5 K = 6
Árbol= { (1, 2), (5, 1), (3, 1), (4, 2) }
Salida: 48
Enfoque:
Vamos a enraizar el árbol en el Node 1, y luego lo pintamos comenzando con la raíz moviéndose hacia abajo hasta las hojas. Para la raíz podemos pintarla con los k colores disponibles. Si la raíz tiene x hijos podemos pintarla con k-1 P x maneras, es decir
(k-1)!/(k-1-x)!. Porque cada niño tiene que usar un color distinto, y todos deben ser diferentes del color usado para la raíz.
Ahora, para los Nodes restantes, pintamos todos los hijos de un Node particular v a la vez. Sus colores tienen que ser distintos y diferentes del color usado para v y el padre de v. Entonces, si v tiene x hijos, podemos pintarlos en k-2 P x formas
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ Implementation of above approach
#include <bits/stdc++.h>
using namespace std;
const int maxx = 1e5;
vector<int> tree[maxx];
int degree_of_node[maxx], parent_of_node[maxx],
child_of_node[maxx], flag = -1;
// Function to calculate number of children
// of every node in a tree with root 1
void dfs(int current, int parent)
{
parent_of_node[current] = parent;
for (int& child : tree[current]) {
// If current and parent are same we have
// already visited it, so no need to visit again
if (child == parent)
return;
dfs(child, current);
}
// If the current node is a leaf node
if (degree_of_node[current] == 1 && current != 1) {
// For leaf nodes there will be no child.
child_of_node[current] = 0;
return;
}
// Gives the total child of current node
int total_child = 0;
for (auto& child : tree[current]) {
if (child == parent)
return;
else
++total_child;
}
child_of_node[current] = total_child;
return;
}
// Function to calculate permutations ( nPr )
int find_nPr(int N, int R)
{
if (R > N) {
flag = 0;
return 0;
}
int total = 1;
for (int i = N - R + 1; i <= N; ++i) {
total = total * i;
}
return total;
}
// Function to calculate the number of ways
// to paint the tree according to given conditions
int NoOfWays(int Nodes, int colors)
{
// Do dfs to find parent and child of a node,
// we root the tree at node 1.
dfs(1, -1);
// Now start iterating for all nodes of
// the tree and count the number of ways to
// paint its children and node itself
int ways = 0;
for (int i = 1; i <= Nodes; ++i) {
// If the current node is root node, then
// we have total of K ways to paint it and
// (k-1)P(x) to paint its child
if (i == 1) {
ways = ways + colors *
find_nPr(colors - 1, child_of_node[1]);
}
else {
// For other remaining nodes which are not
// leaf nodes we have (k-2)P(x) to paint
// its children, we will not take into
// consideration of current node
// since we already painted it.
if (degree_of_node[i] == 1) {
continue;
}
else {
ways = ways *
find_nPr(colors - 2, child_of_node[i]);
}
}
}
return ways;
}
// Function to build the tree
void MakeTree()
{
tree[2].push_back(1);
tree[1].push_back(2);
tree[3].push_back(2);
tree[2].push_back(3);
degree_of_node[2]++;
degree_of_node[1]++;
degree_of_node[3]++;
degree_of_node[2]++;
}
// Driver Code
int main()
{
int N = 3, K = 3;
MakeTree();
int Count = NoOfWays(N, K);
cout << Count << "\n";
return 0;
}
6
Complejidad de tiempo : O(N)