Problem:
 Score : 500 points    Problem Statement You are given a tree with N vertices and N-1 edges. The vertices are numbered 1 to N , and the i -th edge connects Vertex a_i and b_i .  You have coloring materials of K colors.
For each vertex in the tree, you will choose one of the K colors to paint it, so that the following condition is satisfied:   If the distance between two different vertices x and y is less than or equal to two, x and y have different colors.   How many ways are there to paint the tree? Find the count modulo 1\ 000\ 000\ 007 .   What is tree? A tree is a kind of graph. For detail, please see: Wikipedia "Tree (graph theory)"

Solution (Python):
from collections import deque

mod = 10**9+7
n, k = map(int, input().split())
edges = [[] for i in range(n)]
if n == 1:
    print(k)
    exit()
for i in range(n-1):
    a, b = map(int, input().split())
    a-=1
    b-=1
    edges[a].append(b)
    edges[b].append(a)

start = None
for i in range(n):
    if len(edges[i]) == 1:
        start = i
        break

ans = 1
kumi = [0]*n
q = deque()
q.append((start,-1, 1, 0, 0))
while q:
    now, par, par_cnt,par2,child_cnt = q.popleft()
    a = par_cnt
    a *= k - par2 - child_cnt
    a %= mod
    cnt = 0
    for to in edges[now]:
        if to != par:
            if cnt == 0:
                q.append((to, now, a, min(par2+1, 2), 0))
            else:
                q.append((to, now, 1, min(par2+1, 2), cnt))
            cnt += 1
    if cnt == 0:
        ans *= a
        ans %= mod
print(ans)

Solution (Python):
from collections import deque
MOD = 10**9 + 7
N, K = map(int, input().split())
G = [[] for i in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
U = [0]*N
P = [0]*N
que = deque([0])
U[0] = 1
P[0] = -1
ans = K
while que:
    v = que.popleft()
    c = 0
    for w in G[v]:
        if U[w]:
            continue
        U[w] = 1
        que.append(w)
        P[w] = v
        c += 1
    s = 0
    if P[v] != -1:
        s = 2
    else:
        s = 1
    for i in range(c):
        ans = ans * (K-s-i) % MOD
print(ans)

Solution (Python):
from collections import deque
MOD = 10**9 + 7
N, K = map(int, input().split())
G = [[] for i in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
U = [0]*N
P = [0]*N
que = deque([0])
U[0] = 1
P[0] = -1
R = []
ans = K
while que:
    v = que.popleft()
    R.append(v)
    c = 0
    for w in G[v]:
        if U[w]:
            continue
        U[w] = 1
        que.append(w)
        P[w] = v
        c += 1
    s = 0
    if P[v] != -1:
        s = 2
    else:
        s = 1
    for i in range(c):
        ans = ans * (K-s-i) % MOD
print(ans)

Solution (Python):
n,k=map(int,input().split())
mod=10**9+7
edge=[[] for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
fra=[1]*(k+2)
inv=[1]*(k+2)
t=1
for i in range(1,k+2):
    t*=i
    t%=mod
    fra[i]=t
t=pow(fra[k+1],mod-2,mod)
for i in range(k+1,0,-1):
    inv[i]=t
    t*=i
    t%=mod
if max([len(i) for i in edge])+1>k:
    print(0)
    quit()
ans=fra[k]*inv[k-len(edge[1])-1]%mod
q=[1]
c=[0 for i in range(n+1)]
c[1]=1
while len(q)>0:
    t=q.pop()
    for i in edge[t]:
        if c[i]==0:
            ans*=fra[k-2]*inv[k-2-(len(edge[i])-1)]%mod
            ans%=mod
            q.append(i)
            c[i]=1
print(ans)

Solution (Python):
from heapq import heappush, heappop

N, K = map(int, input().split())
a, b = (
    zip(*(map(int, input().split()) for _ in range(N - 1))) if N - 1 else
    ((), ())
)

MOD = 10**9 + 7

G = [set() for _ in range(N + 1)]
for x, y in zip(a, b):
    G[x].add(y)
    G[y].add(x)
q = []
v = [False for _ in range(N + 1)]
heappush(q, (1, 1))
ans = K
v[1] = True
while q:
    i, c = heappop(q)
    X = {x for x in G[i] if not v[x]}
    for l, j in enumerate(X):
        heappush(q, (j, 2))
        ans = (ans * (K - c - l)) % MOD
        v[j] = True

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

N,K=map(int,input().split())
EDGE=[list(map(int,input().split())) for i in range(N-1)]
mod=10**9+7


E=[[] for i in range(N+1)]
for x,y in EDGE:
    E[x].append(y)
    E[y].append(x)

from collections import deque
QUE=deque([1])
ANS=[-1]*(N+1)
ANS[1]=K
count=K

while QUE:
    NQUE=deque()
    while QUE:
        x=QUE.pop()
        if x!=1:
            count=K-1

        for to in E[x]:
            if ANS[to]!=-1:
                continue

            count-=1
            ANS[to]=count
            NQUE.append(to)

    QUE=NQUE

A=1
for a in ANS[1:]:
    A=a*A%mod

print(A)

Solution (Python):
import numpy as np
from collections import deque
from functools import reduce




N, K = map(int, input().split())

edges = [set() for _ in range(N)]
par = [None for _ in range(N)]
flag = [False for _ in range(N)]
neighbors = [0 for _ in range(N)]

for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a-1].add(b-1)
    edges[b-1].add(a-1)

q = deque()
q.append(0)




MOD= 10**9+7
res = K

while len(q) != 0:
    u = q.popleft()
    flag[u] = True
    if par[u] is not None:
        neighbors[par[u]] += 1
        if res != 0:
            res = res*(K-neighbors[par[u]])%MOD
    for v in edges[u]:
        if not flag[v]:
            par[v] = u
            neighbors[v] = 1
            q.append(v)

print(res)

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

sys.setrecursionlimit(100005)

n, k = na()
g = [[] for _ in range(n)]
for i in range(n-1):
    a, b = na()
    g[a-1].append(b-1)
    g[b-1].append(a-1)


def inv(a, mod):
    b = mod
    p, q = 1, 0
    while b > 0:
        c = a//b
        d = a; a = b; b = d % b
        d = p; p = q; q = d-c*q
    return p+mod if p < 0 else p



def dfs(cur, pre, k, g):
    mod = 1000000007
    ret = 1
    nc = 0 if pre == -1 else 1
    for e in g[cur]:
        if e == pre: continue
        nc += 1
        ret = ret * (k-nc) % mod
        ret = ret * dfs(e, cur, k, g) % mod
    return ret % mod


print(dfs(0, -1, k, g) * k % 1000000007)

Solution (Python):
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

P = [-1] * N
Q = [0]
while Q:
    i = Q.pop()
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            Q.append(a)

mod = 10**9+7
fa = [1]
for i in range(1, 10**5+100):
    fa.append(fa[-1]*i%mod)
    
def p(n, k):
    if k > n: return 0
    return fa[n] * pow(fa[n-k], mod-2, mod) % mod

ans = K * p(K-1, len(X[0])) % mod
for i in range(1, N):
    ans = ans * p(K-2, len(X[i])) % mod

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

N,K = map(int,input().split())
MOD = 10 ** 9 + 7

edge = [[] for _ in range(N)]
for _ in range(N-1):
  a,b = map(lambda x: int(x) - 1,input().split())
  edge[a].append(b)
  edge[b].append(a)
deg = [len(E) for E in edge]
  
U = 10 ** 5 + 100
fact = [1] * (U+1)
fact_inv = [1] * (U+1)
for n in range(1,U+1):
  fact[n] = fact[n-1] * n % MOD
fact_inv[U] = pow(fact[U],MOD-2,MOD)
for n in range(U-1,0,-1):
  fact_inv[n] = fact_inv[n+1] * (n+1) % MOD

def perm(n,k):
  if k > n or k < 0:
    return 0
  return fact[n] * fact_inv[n-k] % MOD

def F(x,parent = None):
  if parent is None:
    c = perm(K, deg[x] + 1)
  else:
    c = perm(K-2, deg[x] - 1)
  for y in edge[x]:
    if y == parent:
      continue
    c *= F(y,x)
    c %= MOD
  return c

answer = F(0)
print(answer)