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

2021年4月4日19:22:50 发表评论 924 次浏览

## 本文概述

``````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``````

## 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``