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
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




N,K = IL()
graph = [[] for i in range(N)]
for _ in range(N-1):
  a,b = IL()
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
  
def bfs(graph, start):
  N = len(graph)
  d = [INF] * N
  d[start] = 0
  q = deque([start])
  if len(graph[0]) > K-1:
    return 0
  ans = kaijo(K)*gyaku_kaijo(K-1-len(graph[0]))
  ans %= MOD
  while q:
    u = q.popleft()
    for v in graph[u]:
      if d[v] != INF: continue
      d[v] = d[u] + 1
      if len(graph[v]) > K-1:
        return 0
      if len(graph[v]) != 1:
        ans *= kaijo(K-2)*gyaku_kaijo(K-1-len(graph[v]))
        ans %= MOD
      q.append(v)
  return ans

ans = bfs(graph,0)
print(ans)

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


def read():
    N, K = map(int, input().strip().split())
    G = [[] for i in range(N+1)]
    for i in range(N-1):
        a, b = map(int, input().strip().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    return N, K, G


def permute_init(n, MOD):
    factorial = [1 for i in range(n+1)]
    for i in range(1, n+1):
        factorial[i] = factorial[i-1] * i
        factorial[i] %= MOD
    return factorial


def permute(n, r, factorial, MOD):
    """nPr = n! / (n-r)!"""
    if n < 0 or r < 0 or n < r:
        return 0
    return factorial[n] * pow(factorial[n-r], MOD-2, MOD) % MOD


def solve(N, K, G, MOD=10**9+7):
    factorial = permute_init(K, MOD)

    visited = [False for i in range(N)]
    
    def dfs(a=0):
        f = 1
        if a == 0:
            f = permute(K-1, len(G[a]), factorial, MOD)
        else:
            f = permute(K-2, len(G[a])-1, factorial, MOD)
        for b in G[a]:
            if not visited[b]:
                visited[b] = True
                f *= dfs(b)
                f %= MOD
        return f
    
    visited[0] = True
    ans = K * dfs(0) % MOD

    return ans


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Solution (Python):
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N,K = MI()
mod = 10**9+7

G = {}
for i in range(1,N+1):
    G[i] = []
for i in range(N-1):
    a,b = MI()
    G[a].append(b)
    G[b].append(a)

if max(len(G[i]) for i in range(1,N+1)) >= K:
    print(0)
    exit()


def nPr(n,r):  
    res = 1
    for i in range(r):
        res *= (n-i)
        res %= mod
    return res


from collections import deque

q = deque([(1,0)])  
ans = K
while q:
    n,m = q.pop()
    if m == 0:
        ans *= nPr(K-1,len(G[n]))
        ans %= mod
        for d in G[n]:
            q.appendleft((d,n))
    else:
        ans *= nPr(K-2,len(G[n])-1)
        ans %= mod
        for d in G[n]:
            if d != m:
                q.appendleft((d,n))
print(ans)

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

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

mod = 10**9+7
N = 2*10**5
fac = [1]*(N+1)
finv = [1]*(N+1)
for i in range(N):
    fac[i+1] = fac[i] * (i+1) % mod
finv[-1] = pow(fac[-1], mod-2, mod)
for i in reversed(range(N)):
    finv[i] = finv[i+1] * (i+1) % mod

def prm(n, r, mod):
    if r <0 or r > n:
        return 0
    if r == 0:
        return 1
    return fac[n] * finv[n-r] % mod

s = [0]
visit = [-1]*n
visit[0] = 0
ans = 1
while s:
    v = s.pop()
    if v != 0:
        c = len(g[v])-1
        K = k-2
    else:
        c = len(g[v])+1
        K = k
    ans *= prm(K, c, mod)
    ans %= mod
    for u in g[v]:
        if visit[u] == -1:
            visit[u] = 0
            s.append(u)
print(ans)

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

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

mod = 10**9+7
N = 2*10**5
fac = [1]*(N+1)
finv = [1]*(N+1)
for i in range(N):
    fac[i+1] = fac[i] * (i+1) % mod
finv[-1] = pow(fac[-1], mod-2, mod)
for i in reversed(range(N)):
    finv[i] = finv[i+1] * (i+1) % mod

def prm(n, r, mod):
    if r <0 or r > n:
        return 0
    if r == 0:
        return 1
    return fac[n] * finv[n-r] % mod

s = [0]
visit = [-1]*n
visit[0] = 0
ans = 1
while s:
    v = s.pop()
    if v != 0:
        c = len(g[v])-1
        K = k-2
    else:
        c = len(g[v])+1
        K = k
    ans *= prm(K, c, mod)
    ans %= mod
    for u in g[v]:
        if visit[u] == -1:
            visit[u] = 0
            s.append(u)
print(ans)

Solution (Python):
from collections import defaultdict

class Tree:
    def __init__(self, n, edges, weight=False):
        self.n = n
        self.adj = [[] for _ in range(n)]
        self.parent = [-1] * self.n
        self.children = [[] for _ in range(self.n)]
        self.dist = [0] * self.n  
        self.depth = [0] * self.n  
        self.order = []
        self.weight = defaultdict(lambda: 10**18)
        if weight:
            for u, v, weight in edges:
                self.adj[u].append(v)
                self.adj[v].append(u)
                self.weight[(u, v)] = weight
                self.weight[(v, u)] = weight
        else:
            for u, v in edges:
                self.adj[u].append(v)
                self.adj[v].append(u)
                self.weight[(u, v)] = 1
                self.weight[(v, u)] = 1

    def set_root(self, root):  
        self.order.append(root)
        self.root = root
        stack = [root]
        while stack:
            v = stack.pop()
            for child in self.adj[v]:
                if child == self.parent[v]:
                    continue
                else:
                    self.parent[child] = v
                    self.children[v].append(child)
                    self.dist[child] = self.dist[v] + self.weight[(v, child)]
                    self.depth[child] = self.depth[v] + 1
                    self.order.append(child)
                    stack.append(child)

    def get_root_path(self, target):
        path = [target]
        v = target
        while v != self.root:
            path.append(self.parent[v])
            v = self.parent[v]
        path.reverse()
        return path

    def get_diameter(self, restore=False):  
        u = self.dist.index(max(self.dist))  
        dist_u = [-1] * self.n
        dist_u[u] = 0
        stack = [u]
        parent_u = [None for _ in range(self.n)]
        while stack:
            v = stack.pop()
            for child in self.adj[v]:
                if dist_u[child] == -1:
                    dist_u[child] = dist_u[v] + self.weight[(v, child)]
                    parent_u[child] = v
                    stack.append(child)
        diameter = max(dist_u)
        v = dist_u.index(diameter)
        if restore:
            path = [v]
            while v != u:
                v = parent_u[v]
                path.append(v)
            path.reverse()  
            return diameter, path
        else:
            return diameter, u, v

    

    def heavy_light_decompose(self):  
        self.subsize = [1] * self.n  
        self.head = [self.root] * self.n  
        self.tree_order = [0] * self.n

        
        
        for v in reversed(self.order):
            v_kids = self.children[v]  
            for i, child in enumerate(v_kids):
                self.subsize[v] += self.subsize[child]
                if self.subsize[child] > self.subsize[v_kids[0]]:
                    v_kids[i], v_kids[0] = v_kids[0], v_kids[i]

        
        
        stack = [self.root]
        tree_label = 0
        while stack:
            v = stack.pop()
            self.tree_order[v] = tree_label
            tree_label += 1
            for child in reversed(self.children[v]):  
                if child == self.children[v][0]:
                    self.head[child] = self.head[v]
                else:
                    self.head[child] = child  
                stack.append(child)

    def get_hld_chain_paths(self, u, v):  
        ret = []
        while True:
            if self.tree_order[u] > self.tree_order[v]:
                u, v = v, u
            if self.head[u] == self.head[v]:
                ret.append((self.tree_order[u], self.tree_order[v] + 1))
                return ret
            else:
                ret.append((self.tree_order[self.head[v]], self.tree_order[v] + 1))
                v = self.parent[self.head[v]]

    def get_hld_lca(self, u, v):  
        while True:  
            if self.tree_order[u] > self.tree_order[v]:
                u, v = v, u
            if self.head[u] == self.head[v]:
                return u
            v = self.parent[self.head[v]]

    def get_hld_distance(self, u, v):
        return self.dist[u] + self.dist[v] - (2 * self.dist[self.get_hld_lca(u, v)])

    def exist_on_path_hld(self, u, v, x):  
        return self.get_hld_distance(u, x) + self.get_hld_distance(x, v) == self.get_hld_distance(u, v)



n, k = (int(x) for x in input().split())
edges = [tuple(int(x) - 1 for x in input().split()) for _ in range(n - 1)]
MOD = 10**9 + 7
if n == 1:
    print(k)
    exit()
elif n == 2:
    print(k * (k - 1))
    exit()

tree = Tree(n, edges)
tree.set_root(0)
ans = k
stack = [0]
while stack:
    u = stack.pop()
    if u == tree.root:
        for i, v in enumerate(tree.children[u]):
            ans *= k - 1 - i
            ans %= MOD
            stack.append(v)
    else:
        for i, v in enumerate(tree.children[u]):
            ans *= k - 2 - i
            ans %= MOD
            stack.append(v)

print(ans)

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    edge = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = map(int, input().split())
        edge[a - 1].append(b - 1)
        edge[b - 1].append(a - 1)

    res = k
    que = deque([0])
    visited = [False] * n
    visited[0] = True
    while que:
        v = que.popleft()
        cnt = 0
        for u in edge[v]:
            if not visited[u]:
                visited[u] = True
                cnt += 1
                que.append(u)
        if v == 0:
            for i in range(cnt):
                res *= (k - 1 - i)
                res %= mod
        else:
            for i in range(cnt):
                res *= (k - 2 - i)
                res %= mod
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n, k = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
ans = 1
mod = 10**9+7
def dfs(node, p_node=-1):
    if p_node==-1:
        tmp = k
        kk = k-1
    else:
        tmp = 1
        kk = k-2
    for c_node in graph[node]:
        if c_node==p_node:
            continue
        tmp *= dfs(c_node, node)
        tmp *= kk
        tmp %= mod
        kk -= 1
    return tmp
print(dfs(0))

Solution (Python):
n,k=map(int,input().split())
L=[[] for i in range(n+1)]

for i in range(n-1):
    a,b=map(int,input().split())
    L[a].append(b)
    L[b].append(a)
    
C=[k for i in range(n+1)]
V=[0 for i in range(n+1)]
mod=1_000_000_007
ans=1
que=[(1,0)]
V[1]=1
head=0

cnt=1
while len(que)>head:
    now=que[head]
    head+=1
    ans=ans*(k-now[1])%mod
    for i in range(len(L[now[0]])):
        nex=L[now[0]][i]
        if V[nex]==0:
            V[nex]=1
            que.append((nex,cnt))
            cnt+=1
    cnt=2


print(ans)

Solution (Python):
n,k=map(int,input().split())
ki=[[] for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  ki[a].append(b)
  ki[b].append(a)
mod=pow(10,9)+7
from collections import deque
seen=[-1]*n
seen[0]=k
todo=deque([0])
while todo:
  t=todo.popleft()
  s=max(k-2,seen[t]-1)
  for li in ki[t]:
    if seen[li]==-1:
      if s<=0:
        print(0)
        exit()
      seen[li]=s
      s-=1
      todo.append(li)
ans=1
for s in seen:
  ans*=s
  ans%=mod
print(ans)

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10**6)
n,k=map(int,input().split())
paths=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    paths[a-1].append(b-1)
    paths[b-1].append(a-1)
inf=100000000000000
nums=[-inf]*n
nums[0]=k
from collections import deque
now=deque()
now.append(0)
def bfs(d):
    global n,k,paths,nums,now
    l=len(now)
    if d==1:
        for i in range(l):
            p=now.popleft()
            ln=len(paths[p])
            next_num=k-1
            for j in range(ln):
                if nums[paths[p][j]]==-inf:
                    nums[paths[p][j]]=next_num
                    now.append(paths[p][j])
                    next_num-=1
    else:
        for i in range(l):
            p=now.popleft()
            ln=len(paths[p])
            next_num=k-2
            for j in range(ln):
                if nums[paths[p][j]]==-inf:
                    nums[paths[p][j]]=next_num
                    now.append(paths[p][j])
                    next_num-=1
    if len(now):bfs(d+1)
bfs(1)
ans=1
for i in range(n):
    if nums[i]<=0:
        print(0)
        exit()
    ans*=nums[i]
    ans%=(10**9+7)
print(ans)

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10**6)
n,k=map(int,input().split())
paths=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    paths[a-1].append(b-1)
    paths[b-1].append(a-1)
inf=100000000000000
nums=[-inf]*n
nums[0]=k
from collections import deque
now=deque()
now.append(0)
def bfs(d):
    global n,k,paths,nums,now
    l=len(now)
    if d==1:
        for i in range(l):
            p=now.popleft()
            ln=len(paths[p])
            next_num=k-1
            for j in range(ln):
                if nums[paths[p][j]]==-inf:
                    nums[paths[p][j]]=next_num
                    now.append(paths[p][j])
                    next_num-=1
    else:
        for i in range(l):
            p=now.popleft()
            ln=len(paths[p])
            next_num=k-2
            for j in range(ln):
                if nums[paths[p][j]]==-inf:
                    nums[paths[p][j]]=next_num
                    now.append(paths[p][j])
                    next_num-=1
    if len(now):bfs(d+1)
bfs(1)
ans=1
for i in range(n):
    if nums[i]<=0:
        print(0)
        exit()
    ans*=nums[i]
    ans%=(10**9+7)
print(ans)

Solution (Python):
from collections import deque
N, K = map(int, input().split())
ab = [list(map(int,input().split())) for _ in range(N-1)]
mod = 1000000007

routes = [[] for _ in range(N)]
for i in range(N-1):
    routes[ab[i][0]-1].append(ab[i][1]-1)
    routes[ab[i][1]-1].append(ab[i][0]-1)

options = [0 for i in range(N)]
seen = [False for _ in range(N)]
options[0] = K
seen[0] = True
todo = deque([0])
color = 0
while len(todo):
    checking = todo.pop()
    if checking == 0:
        rest = K
    else:
        rest = K-1
    for route in routes[checking]:
        if seen[route] == False: 
            todo.append(route)
            rest = rest - 1
            options[route] = rest
            seen[route] = True

answer = 1
for i in range(N):
    answer = (answer * options[i])%mod
print(answer)

Solution (Python):
N,K=list(map(int,input().split()))
g=[[] for _ in range(N+1)]

mod=10**9+7

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

visit=[-1]*(N+1)
visit[0]=K

stack=[(0,1,0)]
ans=1


while len(stack)>0:
    parent,current,depth=stack.pop()

    ans*=visit[parent]
    ans%=mod

    if ans==0:
        break

    visit[parent]-=1

    visit[current]=K-min(2,depth+1)
    
    for child in g[current]:
        if visit[child]>-1:
            continue

        stack.append([current,child,depth+1])

print(ans)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






N, K = getNM()
query = [getList() for i in range(N - 1)]

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

fact =[1] 
for i in range(1, K + 1):
    fact.append(fact[i - 1] * i % mod)

facv = [0] * (K + 1) 
facv[-1] = pow(fact[-1], mod - 2 , mod)

for i in range(K - 1, -1, -1):
    facv[i] = facv[i + 1] * (i + 1) % mod

def cmb(n, r):
    if n < r:
        return 0
    return fact[n] * facv[r] * facv[n - r] % mod

max_root = 0
max_root_index = 0
for i in range(N):
    if len(dist[i]) >= max_root:
        max_root = len(dist[i])
        max_root_index = i

pos = deque([max_root_index])

ans = 1
ignore = [-1] * N
ignore[max_root_index] = 1
ans *= cmb(K, max_root + 1) * math.factorial(max_root + 1)

while len(pos) > 0:
    u = pos.popleft()
    for i in dist[u]:
        if ignore[i] == -1:
            ignore[i] = 1
            if len(dist[i]) >= 2:
                ans *= cmb(K - 2, len(dist[i]) - 1) * math.factorial(len(dist[i]) - 1)
                ans %= mod
            pos.append(i)

print(ans % mod)

Solution (Python):
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)

import queue
MOD = 10**9+7

def P(n, m, MOD=10**9+7):
    res = 1
    for i in range(m):
        res *= n - i
        res %= MOD
    return res

r = 0
dp = [1]*N

q = queue.Queue()
q.put((r, -1))
while not q.empty():
    v, p = q.get()
    if v == r: dp[v] = P(K-1, len(G[v]), MOD)
    elif len(G[v]) > 1: dp[v] = P(K-2, len(G[v])-1, MOD)
    for c in G[v]:
        if c == p: continue
        q.put((c, v))

ans = K
for n in dp:
    ans *= n
    ans %= MOD

print(ans)

Solution (Python):
n, k = map(int, input().split())
mod = 10**9+7
data = [[] for j in range(n+1)]
done = [0]*(n+1)
colors = [k-1]*(n+1)

for i in range(n-1):
  a, b = map(int, input().split())
  data[min(a,b)].append(max(a,b))
  data[max(a,b)].append(min(a,b))

queue = [1]
ans = 1
colors[1] += 1
for d in data[1]:
  colors[d] += 1
while queue != []:
  idx = queue.pop(0)
  done[idx] = 1
  ans *= colors[idx]
  ans %= mod
  cnt = 0
  for i in range(len(data[idx])):
    if done[data[idx][i]]:
      continue
    cnt += 1
    colors[data[idx][i]] -= cnt
    queue.append(data[idx][i])

print(ans)

Solution (Python):
from collections import deque
MOD = 10**9+7

def bfs(start, g, visited, k):
    q = deque([start])
    visited[start] = 0
    ans = k
    first_flag = True
    while q:
        curr_node = q.popleft()
        i = 0
        for next_node in g[curr_node]:
            if visited[next_node] >= 0: continue
            if first_flag: 
                ans *= (k-(i+1))
            else:
                ans *= (k-(i+2))
            ans%=MOD
            visited[next_node] = visited[curr_node] + 1
            q.append(next_node)
            i+=1
        first_flag = False
    return ans


n, k = map(int, input().split()) 
g = [ [] for _ in range(n+1)]
visited = [-1] * (n+1)
for i in range(n-1):
    a, b = map(int, input().split()) 
    g[a].append(b)
    g[b].append(a)

ans = bfs(1, g, visited, k)
print(ans)

Solution (Python):


from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
N, K = map(int, input().split())
graph = [[] for i in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
visited = [0 for i in range(N+1)]
dis = [0 for i in range(N+1)]
parent = [-1 for i in range(N+1)]
parent[1] = -1
visited[1] = True
mod = 10**9+7


def bfs(node):
    for child in graph[node]:
        if visited[child] == False:
            visited[child] = True
            parent[child] = node
            dis[child] = dis[node]+1
            bfs(child)


bfs(1)

par_data = defaultdict(int)
for i in range(1, N+1):
    x = parent[i]
    par_data[x] += 1
ans = K
for parent in par_data.keys():
    if parent > 0:
        X = par_data[parent]
        if parent == 1:
            for i in range(X):
                ans = ans*(K-1-i)
                ans %= mod
                if ans==0:
                  print(0)
                  exit()
        else:
            for i in range(X):
                ans = ans*(K-2-i)
                ans %= mod
                if ans==0:
                  print(0)
                  exit()
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7
res = 1


def resolve():
    def dfs(v, p, c):
        global res
        res = (res * c) % mod
        c = k - 1 if p == -1 else k - 2
        for u in edge[v]:
            if u != p:
                dfs(u, v, c)
                c -= 1

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

    dfs(0, -1, k)
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
from collections import deque

N, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N - 1)]

tree = [[] for _ in range(N + 1)]
for a, b in X:
    tree[a].append(b)
    tree[b].append(a)

MAX = 10 ** 5 + 1
MOD = 10 ** 9 + 7


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

finv = [0] * (MAX + 1)
finv[MAX] = pow(fac[MAX], MOD - 2, MOD)
for i in reversed(range(1, MAX + 1)):
    finv[i - 1] = finv[i] * i % MOD

def comb(n, k):
    if n < k or k < 0:
        return 0
    return (fac[n] * finv[k] * finv[n - k]) % MOD

visited = [False] * (N + 1)
visited[0] = True
visited[1] = True
stack = deque([1])
ans = K
while stack:
    u = stack.popleft()
    child_num = sum(not visited[v] for v in tree[u])
    ans *= comb(K - 1 - int(u != 1), child_num) * fac[child_num]
    ans %= MOD
    for v in tree[u]:
        if not visited[v]:
            visited[u] = True
            stack.append(v)

print(ans)

Solution (Python):

import sys
def main(N, K, G):
    fu = FactorialUtils(K)
    p = [-1] * N
    p[0] = 0
    stk = [0]
    ans = Mint(K)
    while stk:
        v = stk.pop()
        t = 1 if v != 0 else 0
        ans *= fu.permutation(K - t - 1, len(G[v]) - t)
        for to in G[v]:
            if p[to] >= 0:
                continue
            p[to] = v
            stk.append(to)
    print(ans)

MOD = 10**9 + 7
class FactorialUtils:
    def __init__(self, n):
        self.fac = [1] * (n + 1)
        self.ifac = [1] * (n + 1)
        for i in range(2, n + 1): self.fac[i] = self.fac[i - 1] * i % MOD
        self.ifac[n] = pow(self.fac[n], MOD - 2, MOD)
        for i in range(n, 1, -1): self.ifac[i - 1] = self.ifac[i] * i % MOD

    def choose(self, n, r):
        if r < 0 or r > n: return 0
        return (self.fac[n] * self.ifac[n - r] % MOD) * self.ifac[r] % MOD

    def multichoose(self, u, k):
        return (self.fac[u + k - 1] * self.ifac[u - 1] % MOD) * self.ifac[k] % MOD

    def permutation(self, n, r):
        if r < 0 or r > n: return 0
        return self.fac[n] * self.ifac[n - r] % MOD

class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % MOD
        return self

    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other)) % MOD
        if self.value < 0: self.value += MOD
        return self

    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj

    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self

    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self

    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj

    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj

if __name__ == '__main__':
    input = sys.stdin.readline
    N, K = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        x, y = map(int, input().split())
        x, y = x - 1, y - 1
        G[x].append(y)
        G[y].append(x)
    main(N, K, G)

Solution (Python):
import sys


sys.setrecursionlimit(10 ** 6)


def main():
    MOD = 10 ** 9 + 7
    N, K = list(map(int, input().split(' ')))
    adj = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = list(map(lambda x: int(x) - 1, input().split(' ')))
        adj[a].append(b)
        adj[b].append(a)
    if K <= 2:
        if N <= K:
            p = 1
            for n in range(N):
                p *= K - n
            print(p % MOD)
        else:
            print(0)
        return
    p = 1
    perm_k1 = [0 for _ in range(K)]
    for k in range(K):
        perm_k1[k] = p
        p *= K - 1 - k
        p %= MOD
    perm_k2 = [0 for _ in range(K - 1)]
    p = 1
    for k in range(K - 1):
        perm_k2[k] = p
        p *= K - 2 - k
        p %= MOD

    def dfs(n=0, p=-1):
        
        children = [c for c in adj[n] if c != p]
        if len(children) == 0:
            return 1
        n_colors = K - 2 if n != 0 else K - 1
        if n_colors < len(children):
            return 0
        ret = perm_k2[len(children)] if n != 0 else perm_k1[len(children)]
        for c in children:
            ret *= dfs(c, n)
            ret %= MOD
        return ret

    print((K * dfs()) % MOD)


if __name__ == '__main__':
    main()