为偏斜树着色的方法，以使父级和子级具有不同的颜色

本文概述

• C ++
• Java
• Python3
• C#
• 的PHP

给定一个带有N个节点和K种颜色的偏斜树(每个节点最多有一个孩子)。你必须为每个节点分配从1到K的颜色, 以便父级和子级具有不同的颜色。找出最大数量方法为节点着色。

例子 -

Input : N = 2, K = 2.
Output :  
Let A1 and A2 be the two nodes.
Let A1 is parent of A2.
Colors are Red and Blue.
Case 1: A1 is colored Red 
       and A2 is colored Blue.
Case 2: A1 is colored Blue 
       and A2 is colored Red.
No. of ways : 2      

Input : N = 3, K = 3.
Output : 
A1, A2, A3 are the nodes. 
A1 is parent of A2 
and A2 is parent of A3.
Let colors be R, B, G.
A1 can choose any three colors 
and A2 can choose 
any other two colors
and A3 can choose 
any other two colors 
than its parents.
No. of ways: 12

注意，只有根节点和子节点(子节点、孙节点、孙节点....)和所有)应该有不同的颜色。树的根可以选择K种颜色中的任意一种K种方法。每个其他节点都可以选择除其父节点以外的K-1种颜色。每个节点有K-1个选项。

在这里, 我们选择树作为每个节点, 只有一个孩子。我们可以选择K种颜色中的任何一种作为树的根, 因此采用K种方式。我们为它的孩子留下了K-1颜色。因此, 对于每个孩子, 我们都可以为其父母分配其他颜色。因此, 对于N-1个节点中的每一个, 我们剩下K-1种颜色。因此答案是K *(K-1)^(N-1).

我们可以通过使用耗费O(N)时间复杂度的普通幂函数来找到答案。但是为了获得更好的时间复杂度, 我们使用了快速指数函数, 该函数需要O(log N)时间复杂度。

C ++

// C++ program to count number of ways to color
// a N node skewed tree with k colors such that
// parent and children have different colors.
#include <bits/stdc++.h>
using namespace std;
  
// fast_way is recursive
// method to calculate power
int fastPow( int N, int K)
{
     if (K == 0)
         return 1;
     int temp = fastPow(N, K / 2);
     if (K % 2 == 0)
         return temp * temp;
     else
         return N * temp * temp;
}
  
int countWays( int N, int K)
{
     return K * fastPow(K - 1, N - 1);
}
  
// driver program
int main()
{
     int N = 3, K = 3;
     cout << countWays(N, K);
     return 0;
}

Java

// Java program to count number of ways to color
// a N node skewed tree with k colors such that
// parent and children have different colors.
import java.io.*;
  
class GFG {
     // fast_way is recursive
     // method to calculate power
     static int fastPow( int N, int K)
     {
         if (K == 0 )
             return 1 ;
         int temp = fastPow(N, K / 2 );
         if (K % 2 == 0 )
             return temp * temp;
         else
             return N * temp * temp;
     }
  
     static int countWays( int N, int K)
     {
         return K * fastPow(K - 1 , N - 1 );
     }
  
     // Driver program
     public static void main(String[] args)
     {
         int N = 3 , K = 3 ;
         System.out.println(countWays(N, K));
     }
}
  
// This code is contributed by vt_m.

Python3

# Python3 program to count  
# number of ways to color 
# a N node skewed tree with 
# k colors such that parent 
# and children have different 
# colors.
  
# fast_way is recursive
# method to calculate power
def fastPow(N, K):
     if (K = = 0 ):
         return 1 ;
      
     temp = fastPow(N, int (K / 2 ));
     if (K % 2 = = 0 ):
         return temp * temp;
     else :
         return N * temp * temp;
  
def countWays(N, K):
     return K * fastPow(K - 1 , N - 1 );
  
# Driver Code
N = 3 ; 
K = 3 ;
print (countWays(N, K));
  
# This code is contributed by mits

C#

// C# program to count number of ways
// to color a N node skewed tree with
// k colors such that parent and
// children  have different colors
using System;
  
class GFG {
  
     // fast_way is recursive
     // method to calculate power
     static int fastPow( int N, int K)
     {
         if (K == 0)
             return 1;
         int temp = fastPow(N, K / 2);
         if (K % 2 == 0)
             return temp * temp;
         else
             return N * temp * temp;
     }
  
     static int countWays( int N, int K)
     {
         return K * fastPow(K - 1, N - 1);
     }
  
     // Driver code
     public static void Main()
     {
         int N = 3, K = 3;
         Console.WriteLine(countWays(N, K));
     }
}
  
// This code is contributed by vt_m.

的PHP

<?php
// PHP program to count number 
// of ways to color a N node 
// skewed tree with k colors 
// such that parent and children
// have different colors.
  
// fast_way is recursive
// method to calculate power
function fastPow( $N , $K )
{
     if ( $K == 0)
         return 1;
          
     $temp = fastPow( $N , $K / 2);
      
     if ( $K % 2 == 0)
         return $temp * $temp ;
     else
         return $N * $temp * $temp ;
}
  
function countWays( $N , $K )
{
     return $K * fastPow( $K - 1, $N - 1);
}
  
     // Driver Code
     $N = 3; 
     $K = 3;
     echo countWays( $N , $K );
  
// This code is contributed by ajit
?>

输出：

12

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。