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):



import sys
sys.setrecursionlimit(10 ** 6)


class FactorialMod:
    def __init__(self, prime, max_size):
        self.prime = prime
        self.max_size = max_size * 2
        self.fac = [0] * self.max_size
        self.finv = [0] * self.max_size
        self.factInit()

    def invMod(self, a):
        b, x, y = self.prime, 1, 0
        while b:
            t = a // b
            a -= t * b
            a, b = b, a
            x -= t * y
            x, y = y, x
        return x % self.prime

    def factInit(self):
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        for i in range(2, self.max_size):
            self.fac[i] = (self.fac[i - 1] * i) % self.prime
            self.finv[i] = (self.finv[i - 1] * self.invMod(i)) % self.prime
    
    def fact(self, n):
        return self.fac[n]
    
    def factInv(self, n):
        return self.finv[n]
    

class Tree:
    def __init__(self, n):
        self.nodes = n
        self.parent = [-1 for _ in range(n + 1)]
        self.children = [[] for _ in range(n + 1)]
        self.edge = [[] for _ in range(n + 1)]
        self.depth = [0 for _ in range(n + 1)]
        self.root = -1
        self.max_depth = -1
    
    def addEdge(self, x, y):
        self.edge[x].append(y)
        self.edge[y].append(x)
    
    def prepare(self):
        checking = [i for i in range(self.nodes, 0, -1)]
        searching = [checking.pop()]
        next_level = []
        while searching:
            p = searching.pop()
            if self.root == -1:
                self.root = p
            cs = self.edge[p]
            self.children[p] = cs
            next_level.extend(cs)
            pd = self.depth[p]
            for c in cs:
                self.parent[c] = p
                self.depth[c] = pd + 1
                self.edge[c].remove(p)
            if searching == []:
                searching = next_level
        self.max_depth = max(self.depth)

    def getParent(self, x):
        return self.parent[x]
    
    def getRoot(self):
        if self.root != -1:
            return self.root
        for x in range(1, self.nodes + 1):
            if self.getParent(x) == -1:
                self.root = x
                return x
    
    def isRoot(self, x):
        return x == self.getRoot()

    def getChildren(self, x):
        return self.children[x]
    
    def getMaxDepth(self):
        return self.max_depth


def solve():
    PRIME = 10 ** 9 + 7
    N, K = list(map(int, input().split()))
    tree = Tree(N)
    f = FactorialMod(PRIME, K)
    for _ in range(N - 1):
        x, y = list(map(int, input().split()))
        tree.addEdge(x, y)
    tree.prepare()
    ans = 1
    searching = []
    next_searching = [[tree.getRoot()]]
    for i in range(tree.getMaxDepth() + 1):
        
        searching = next_searching[:]
        next_searching = []
        
        colors = K - min(2, i)  
        
        while searching:
            brothers = searching.pop()
            if colors < len(brothers):
                
                
                return 0
            ans *= f.fact(colors) * f.factInv(colors - len(brothers))
            ans %= PRIME
            
            for x in brothers:
                children = tree.getChildren(x)
                if children != []:
                    next_searching.append(children)
    return ans % PRIME


def main():
    print(solve())


if __name__ == "__main__":
    main()

Solution (Python):
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

N,K = map(int,input().split())
graph = list([] for _ in range(N))
for i in range(N-1):
    a,b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
def f(x,y):
    r = 1
    for i in range(y):
        r = (r*(x-i))%mod
    return r
q = graph[0]
V = {0}
ans = f(K-1,len(q))
while q:
    v = q.pop()
    if v in  V:
        continue
    V.add(v)
    q += graph[v]
    ans = (f(K-2,len(graph[v])-1)*ans)%mod
print((K*ans)%mod)

Solution (Python):
n,k=map(int,input().split());x,t,e,c=10**9+7,[set()for _ in range(n)],enumerate,k;import sys;sys.setrecursionlimit(x)
for i in range(n-1):a,b=map(int,input().split());t[a-1].add(b);t[b-1].add(a)
def b(o):
  global c
  for i,j in e(t[o-1]):c=(c*(k-2-i))%x;t[j-1].discard(o);b(j)
for i,j in e(t[0]):c=(c*(k-1-i))%x;t[j-1].discard(1);b(j)
print(c)

Solution (Python):
x=10**9+7;import sys;sys.setrecursionlimit(x);n,k=map(int,input().split());t=[set()for _ in range(n)];c=k
for i in range(n-1):a,b=map(int,input().split());t[a-1].add(b);t[b-1].add(a)
def b(o):
  global c
  for i,j in enumerate(t[o-1]):c=(c*(k-2-i))%x;t[j-1].discard(o);b(j)
for i,j in enumerate(t[0]):c=(c*(k-1-i))%x;t[j-1].discard(1);b(j)
print(c)

Solution (Python):
from collections import defaultdict, deque

N, K = map(int, input().split())
M = 10**9 + 7
e = defaultdict(list)
for i in range(N-1):
    a, b = map(int, input().split())
    e[a].append(b)
    e[b].append(a)

d = deque()
d.appendleft((1, -1))
ans = K
while d:
    now, prev = d.pop()
    num_next = len(e[now])
    num_next = 0
    for v in e[now]:
        if(v != prev):
            d.appendleft((v, now))
            num_next += 1
            
    if(prev == -1):
        num_color = K-1
    else:
        num_color = K-2
        
    for i in range(num_next):
        ans *= (num_color-i)
        ans %= M
        
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
mod = 10**9+7
N, K = map(int, input().split())
g = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
def dfs(K, g, now, from_):
    if from_ == -1:
        can_num = K - 1
    else:
        can_num = K - 2
    if K < len(g[now]):
        return 0
    case_num = 1
    for i in g[now]:
        if i != from_:
            case_num *= can_num
            can_num -= 1
            case_num %= mod
    for i in g[now]:
        if i != from_:
            case_num *= dfs(K, g, i, now)
            case_num %= mod
    return case_num
print(K * dfs(K, g, 0, -1) % mod)

Solution (Python):
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(a-1)]
d=[[]for i in range(a)]
for i in range(a-1):
  ca=c[i][0]
  cb=c[i][1]
  d[ca-1].append(cb-1)
  d[cb-1].append(ca-1)
g=[0 for i in range(a)]
q=[]
q.append(0)
e=b
while not q==[]:
  i=q.pop()
  h=len(d[i])
  g[i]=1
  if i==0:
      f=b-1
  else:
    f=b-2
  g[i]=1
  for j in range(h):
    if g[d[i][j]]==0:
      q.append(d[i][j])
      e=(e*f)%1000000007
      f-=1


print(e%1000000007)

Solution (Python):
from collections import deque
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(a-1)]
d=[[]for i in range(a)]
for i in range(a-1):
  ca=c[i][0]
  cb=c[i][1]
  d[ca-1].append(cb-1)
  d[cb-1].append(ca-1)
g=[0 for i in range(a)]
q=deque()
q.append(0)
e=b
while len(q):
  i=q.pop()
  h=len(d[i])
  g[i]=1
  if i==0:
      f=b-1
  else:
    f=b-2
  g[i]=1
  for j in range(h):
    if g[d[i][j]]==0:
      q.append(d[i][j])
      e=(e*f)%1000000007
      f-=1


print(e%1000000007)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
n,k=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
MOD=10**9+7
def coloring(node,pre):
  if len(graph[node])>k:
    return 0
  if pre==-1:
    color=k-1
  else:
    color=k-2
  ans=1
  for i in graph[node]:
    if i==pre:continue
    ans*=color
    ans%=MOD
    color-=1
  for i in graph[node]:
    if i==pre:continue
    ans*=coloring(i,node)
    ans%=MOD
  return ans
print((k*coloring(0,-1))%MOD)

Solution (Python):
import queue

n, k = map(int, input().split())
edges = []
for _ in range(n-1):
  edges.append(list(map(int, input().split())))
mod = 10**9+7

edge_dict = {}
for i in range(1, n+1):
  edge_dict[i] = set()

for edge in edges:
  edge_dict[edge[0]].add(edge[1])
  edge_dict[edge[1]].add(edge[0])

visited = set()
q = queue.LifoQueue()
q.put(1)

num_cases = 1
while not q.empty():
  node = q.get()
  
  visited.add(node)
  num_available_colors = k -2 if node is not 1 else k -1
  
  for child in (edge_dict[node] - visited):
    num_cases *= num_available_colors
    num_available_colors -= 1
    num_cases %= mod
    q.put(child)

print((k*num_cases)%mod)

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

N,K = (int(i) for i in input().split())  
AB = [[int(i) for i in input().split()] for i in range(N-1)] 

Tree = [[] for _ in range(N+1)]
d = deque()

for i in range(N-1):
    a, b = AB[i]
    Tree[a].append(b)
    Tree[b].append(a)

answer = K

for i in range(len(Tree[1])):
    answer = (answer * (K - 1 - i))%(int(10**9)+7)
    d.append([1, Tree[1][i]])

Tree[1] = []

while d != deque():
    for i in range(len(d)):
        parent, child = d[0]
        Tree[child].pop(Tree[child].index(parent))
        for j in range(len(Tree[child])):
            d.append([child, Tree[child][j]])
            answer = (answer * (K - 2 - j))%(int(10**9)+7)
        d.popleft()
print(answer)

Solution (Python):
from collections import deque
from functools   import reduce

modulo = 10 ** 9 + 7

N, K = map(int, input().split())
adj = {a: [] for a in range(1, N + 1)}
for i in range(N - 1):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)

def P(n, k):
    return 0 if n < k else \
           reduce(lambda a, i: a * i % modulo, range(n, n - k, -1), 1)

visited = set()
q = deque([1])
ncoloring = K  

while len(q) > 0:
    u = q.popleft()
    visited.add(u)

    
    children = [c for c in adj[u] if c not in visited]
    ncoloring *= P(K - 1 if u == 1 else K - 2, len(children))
    ncoloring %= modulo

    q.extend([c for c in children])

print(ncoloring)

Solution (Python):
from collections import deque

modulo = 10 ** 9 + 7

N, K = map(int, input().split())
adj = {a: [] for a in range(1, N + 1)}
for i in range(N - 1):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)

def P(n, k):
    if n < k:
        return 0
    f = 1
    for i in range(n, n - k, -1):
        f = f * i % modulo
    return f

visited = set()
q = deque([1])
ncoloring = K  

while len(q) > 0:
    u = q.popleft()
    visited.add(u)

    
    children = [c for c in adj[u] if c not in visited]
    ncoloring *= P(K - 1 if u == 1 else K - 2, len(children))
    ncoloring %= modulo

    q.extend([c for c in children])

print(ncoloring)

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


N,K = map(int,input().split())
used = [0] * N
mod = 10 ** 9 + 7

edge_dic = {i:[] for i in range(N)}
for i in range(N-1):
    a , b = map(int,input().split())
    a -= 1
    b -= 1
    edge_dic[a].append(b)
    edge_dic[b].append(a)



node_queue = deque()

node_queue.append(0)
ans = K
while len(node_queue):
    node = node_queue.pop()
    used[node] = 1
    if node == 0:
        can_use = K - 1
    else:
        can_use = K - 2
    for node_next in edge_dic[node]:
        if used[node_next] == 0:
            node_queue.append(node_next)
            if can_use <= 0:
                print(0)
                exit()
            ans = ans * can_use % mod
            can_use -= 1
print(ans)

Solution (Python):
N,K = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for i in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

MOD = 10**9+7

fac = [1,1] + [0]*K
finv = [1,1] + [0]*K
inv = [0,1] + [0]*K
for i in range(2,K+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def npr(n,r):
    if n<r: return 0
    return fac[n] * finv[n-r]

ans = K * npr(K-1,len(es[0]))
ans %= MOD

visited = [0]*N
visited[0] = 1
stack = []
for v in es[0]:
    stack.append(v)

while stack:
    v = stack.pop()
    visited[v] = 1
    ans *= npr(K-2, len(es[v])-1)
    ans %= MOD
    for to in es[v]:
        if visited[to]: continue
        stack.append(to)
print(ans%MOD)

Solution (Python):
from collections import deque

mod = 10 ** 9 + 7

n, k = map(int, input().split())

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

dq = deque()
dq.append((0, -1))
ans = k

while dq:
    v, pr = dq.popleft()
    can_use_color = k - 1 - (0 if pr == - 1 else 1)

    for u in g[v]:
        if u == pr:
            continue
        ans *= can_use_color
        ans %= mod
        can_use_color -= 1

    for u in g[v]:
        if u == pr:
            continue
        dq.append((u, v))

print(ans)

Solution (Python):

import sys
from collections import deque
import copy

N,K=map(int, sys.stdin.readline().split())

 
mod=10**9+7
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, K+1):
    fact_tmp *= i
    fact_tmp %= mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))

def npr(n,r):
	if n < 0 or r < 0 or n < r:	return 0
	else:	return (fact[n] * inv_fact[n-r]) %mod



nl=[ [] for i in range(N+1) ]	
C=[ 0 for i in range(N+1) ]	
 
for i in range(N-1):
	a,b=map(int, sys.stdin.readline().split())
	nl[a].append(b)
	C[a]+=1
	nl[b].append(a)
	C[b]+=1


start=1
Visit=[ None for i in range(N+1) ] 
Visit[start]=1
 
p=None		
q=deque()
q.append( (p,start) )

ans=K

while q:
	p,current=q.popleft()
	flag=0
	for to in nl[current]:
		if Visit[to] is None:
			Visit[to]=1
			q.append( (current,to) )
			flag=1
	if p is None and flag:
		ans*=npr(K-1,C[current])
	elif p is not None and flag:
		ans*=npr(K-2,C[current]-1)
	ans%=mod
		

print ans

Solution (Python):
mod = 10 ** 9 + 7
n, k = map(int, input().split())
p = []
for _ in range(n-1):
    p.append(list(map(int, input().split())))
l = [[] for _ in range(n+1)]
for pi in p:
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])

ans = k
from _collections import deque
q = deque()
q.append(1)

h = 0
done = [0] * (n+1)
done[1] = 1
while q:
    
    r = q.popleft()
    h += 1
    if h <= 1:
        tmp = k-1
    else:
        tmp = k-2
    for s in l[r]:
        if done[s] == 0:
            q.append(s)
            done[s] = 1
            ans = (ans * tmp) % mod
            tmp -= 1
print(ans)

Solution (Python):
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict






INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)









N, K = [int(x) for x in input().split()]


G = [[] for _ in range(N)]

for _ in range(N - 1):
    a, b = [int(x) for x in input().split()]
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)


def len12(g, st):
    cnt = len(g[st])
    for n1 in g[st]:
        cnt += (len(g[n1]) - 1)
    return cnt


G2 = [[] for _ in range(N)]
opened = set()
opened.add(0)
closed = set()

ans = K
while len(opened) != 0:
    target = opened.pop()
    closed.add(target)
    for n in G[target]:
        if n in closed:
            continue
        opened.add(n)
        G2[target].append(n)
        G2[n].append(target)
        cnt = len12(G2, n)
        ans = ans * (K - cnt)
        ans %= MOD

print(ans)

Solution (Python):
from collections import defaultdict as ddydd
from collections import deque as dq
N, K = map(int, input().split())
mod = 10 ** 9 + 7
Tree = ddydd(list)
for _ in range(N - 1):
  a, b = map(int, input().split())
  Tree[a].append(b)
  Tree[b].append(a)
Q = dq(list())
visited = [0] * (N + 1)
visited[1] = 1
res = K
temp = K - 1
for n in Tree[1]:
  visited[n] = 1
  Q.append(n)
  res *= temp
  res = res % mod
  temp -= 1

while Q:
  n = Q.popleft()
  temp = K - 2
  for m in Tree[n]:
    if visited[m] == 0:
      visited[m] = 1
      Q.append(m)
      res *= temp
      res = res % mod
      temp -= 1
print(res)

Solution (Python):
N,K=map(int,input().split())
mod=1000000007
path=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  path[a].append(b)
  path[b].append(a)

  
abc=[False for i in range(N)] 

abc[0]=True
cnt=0
ans=K%mod
nx=[]
for i in range(len(path[0])):
  child=path[0][i]
  if abc[child]:
    continue
  ans=ans*(K-1-cnt)
  ans=ans%mod
  cnt=cnt+1
  abc[child]=True
  nx.append(child)
while len(nx)>0:
  a=nx.pop()
  cnt=0
  for i in range(len(path[a])):
    child=path[a][i]
    if abc[child]:
      continue
    ans=ans*(K-2-cnt)
    ans=ans%mod
    cnt=cnt+1
    abc[child]=True
    nx.append(child)
      
print(ans%mod)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)
N, K = map(int, input().split())

lis = [[] for i in range(N + 1)]

for n in range(N - 1):
    a, b = map(int, input().split())
    lis[a].append(b)
    lis[b].append(a)

MOD = 10 ** 9 + 7

def dfs(pos, from_, K, lis):
    if from_ == -1:
        to_multi = K - 1
    else:
        to_multi = K - 2
    if len(lis[pos]) > K:
        return 0

    ans = 1
    for item in lis[pos]:
        if item != from_:
            ans *= to_multi
            to_multi -= 1
            ans %= MOD
    for item in lis[pos]:
        if item != from_:
            ans *= dfs(item, pos, K, lis)
            ans %= MOD
    
    return ans

print(K * dfs(1, from_=-1, K=K, lis=lis) % MOD)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(1000000007)
input = sys.stdin.readline

MOD = 1000000007

class Node:
    def __init__(self):
        self.check = False
        self.link = []

    def color(self, K):
        self.check = True
        ret = 1
        
        for i in range(len(self.link)-1):
            ret *= (K - 2) - i
            ret %= MOD
        
        for node in self.link:
            if not node.check:
                ret *= node.color(K)
                ret %= MOD
        return ret

def main():
    N, K = map(int, input().split())
    if N == 1:
        print(K)
    else:
        nodes = [Node() for i in range(N+1)]
        for i in range(N-1):
            a, b = map(int, input().split())
            a -= 1; b -= 1;
            nodes[a].link.append(nodes[b])
            nodes[b].link.append(nodes[a])
        root = nodes[0]
        root.check = True
        ans = K
        for i in range(1, len(root.link)+1):
            ans *= (K-i)
            ans %= MOD
        for node in root.link:
            ans *= node.color(K)
            ans %= MOD
        print(ans)

if __name__ == "__main__":
    main()