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)
mod = 10**9 + 7


def solve(now, from_, K, ab):
    if from_ == -1:
        can_num = K - 1
    else:
        can_num = K - 2
    if K < len(ab[now]):
        return 0
    case_num = 1
    for i in ab[now]:
        if i != from_:
            case_num *= can_num
            can_num -= 1
            case_num %= mod
    for i in ab[now]:
        if i != from_:
            case_num *= solve(i, now, K, ab)
            case_num %= mod
    return case_num


def main():
    N, K = map(int, input().split())
    if N == 1:
        print(K)
        exit(0)
    ab = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        ab[a - 1].append(b - 1)
        ab[b - 1].append(a - 1)
    ans = K * solve(0, -1, K, ab)
    print(ans % mod)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict

class permnk_mod(object):
    
    
    
    
    def __init__(self, maxn, p):
        self.maxn = maxn
        self.p = p
        self.x = [1] 
        self.y = [1] 
        for i in range(1, self.maxn + 1):
            self.x.append(self.x[-1] * pow(i, self.p - 2, self.p) % self.p)
            self.y.append(self.y[-1] * i % self.p)

    def permnk(self, n, k):
        if n < k:
            return 0
        return (self.x[n - k] * self.y[n]) % self.p

def dfs(i, V, E, k):
    MOD = 10 ** 9 + 7
    p = permnk_mod(k - 1, MOD)
    ans = k
    V[i] = 1
    S = [i]
    while(len(S) > 0):
        vi = S.pop()
        for j in E[vi]:
            if V[j] == 0:
                V[j] = 1
                S.append(j)
        if vi == i:
            ans *= p.permnk(k - 1, len(E[vi]))
        elif len(E[vi]) > 1:
            ans *= p.permnk(k - 2, len(E[vi]) - 1)
        ans %= MOD
    return ans

n, k = map(int, input().split())
E = defaultdict(list)
for i in range(n - 1):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
V = [0] * (n + 1)
ans = dfs(1, V, E, k)
print(ans)

Solution (Python):
import sys;sys.setrecursionlimit(100000);n,k=map(int,input().split());x,t,e,c=10**9+7,[set()for _ in range(n)],enumerate,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 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):
import sys;sys.setrecursionlimit(100000);n,k=map(int,input().split());x,t,e=10**9+7,[set()for _ in range(n)],enumerate
for i in range(n-1):a,b=map(int,input().split());t[a-1].add(b);t[b-1].add(a)
c=k
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):
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 7)
graph = defaultdict(list)

N, K = map(int, input().split())
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 dfs(fro, to, f):
    caseNum = f
    colorNum = K - 1 if f == K else K - 2
    for u in graph[fro]:
        if u == to:
            continue
        pat = dfs(u, fro, colorNum)
        if pat == 0:
            caseNum = 0
            break
        caseNum = caseNum * pat % mod
        colorNum -= 1
    return caseNum


ans = dfs(0, -1, K)
print(ans)

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

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

mod = 10 ** 9 + 7


def dfs(v, bf):
    if bf == -1:
        can_use = k - 1
    else:
        can_use = k - 2

    if k <= len(es[v]):
        return 0
    else:
        case_num = 1
        for nv in es[v]:
            if nv == bf: continue
            case_num *= can_use
            case_num %= mod
            can_use -= 1

        for nv in es[v]:
            if nv == bf: continue
            case_num *= dfs(nv, v)
            case_num %= mod

    return case_num


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

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

ans = k * dfs(0, -1) % mod
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

mod = 10 ** 9 + 7


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


def dfs(v, bf):
    global ans
    if v == 0:
        ans *= p(k, len(es[v]) + 1)
        ans %= mod
    else:
        ans *= p(k - 2, len(es[v]) - 1)
        ans %= mod

    for nv in es[v]:
        if nv == bf: continue
        dfs(nv, v)


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

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

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

invs = [None] * (k + 1)
invs[k] = pow(fact[-1], mod - 2, mod)
for i in range(k - 1, -1, -1):
    invs[i] = invs[i + 1] * (i + 1) % mod

ans = 1
dfs(0, -1)
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10**9)

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

mo = 1000000007
ret = 1
E = [[] for _ in range(n)]

def dfs(cur, pre, cand):
    global ret
    ret = (ret % mo * (cand % mo)) % mo
    k = 0
    if pre != -1:
        k = 1
    cand = K - 1 - k
    for e in E[cur]:
        if e != pre:
            dfs(e, cur, cand)
            cand -= 1

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

dfs(0, -1, K)
print(ret % mo)

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

for edge in edges:
    a, b = edge
    a -= 1
    b -= 1
    nodes[a].append(b)
    nodes[b].append(a)

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

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

Solution (Python):
from queue import PriorityQueue
import sys

sys.setrecursionlimit(10**9)

IA = lambda: [int(x) for x in input().split()]
IM = lambda N: [IA() for _ in range(N)]



ans=0
MOD = 1000000007

def dfs(u,fa,k):
    temp=k
    if(fa==0): temp-=1
    else: temp-=2
    global ans
    global MOD
    vis[u]=1
    i=0
    for  v in a[u]:
        if(vis[v]==1):continue
        ans=(ans%MOD*(temp-i)%MOD)%MOD
        dfs(v,u,k)
        i+=1


IA = lambda: [int(x) for x in input().split()]
IM = lambda N: [IA() for _ in range(N)]

n,k = IA()
ans=k
a=[ [] for i in range(0,n+1)]
vis=[int(0) for i in range(0,n+1)]

for i in range(0,n-1):
     u,v=IA()
     a[u].append(v)
     a[v].append(u)

dfs(1,0,k)
print(ans)

Solution (Python):



IA = lambda: [int(x) for x in input().split()]
IM = lambda N: [IA() for _ in range(N)]

N, K = IA()
AB = IM(N - 1)

P = 1000000007

tree = {}
for a, b in AB:
    tree.setdefault(a, set()).add(b)
    tree.setdefault(b, set()).add(a)


def f(root):
    stack = [(None, None, root, K - 1)]
    v = K
    while stack:
        grand_parent, parent, current, k = stack.pop()

        for i, child in enumerate(tree[current] - {parent}):
            v = v * (k - i) % P
            stack.append((parent, current, child, K - 2))
    return v


print(f(AB[0][0]) if AB else K)

Solution (Python):
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Solution (Python):
import sys
from collections import defaultdict

sys.setrecursionlimit(10**5)

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

def culc_tree(t, used_num):
    tree[t][1] = False
    global answer
    k = K - used_num
    answer = (answer * k) % (10 ** 9 + 7)
    childs = [next_ for next_ in tree[t][0] if tree[next_][1]]
    for i, child in enumerate(childs, 2):
        culc_tree(child, i)


tree = defaultdict(lambda: [[], True])
for a, b in a_bs:
    tree[a][0].append(b)
    tree[b][0].append(a)

answer = K
tree[1][1] = False
for i, child in enumerate(tree[1][0], 1):
    culc_tree(child, i)
print(answer)

Solution (Python):
import sys, collections
sys.setrecursionlimit(10000000)

def permutation(k, r, fact, revfact, mod):
    return (fact[k] * revfact[k-r]) % mod

def dfs(now, parent, edge, mod, K, fact, revfact):
    son = 0
    ans = 1
    for next in edge[now]:
        if next != parent:
            son += 1
            ans *= dfs(next, now, edge, mod, K, fact, revfact)
            ans %= mod
    if K-2 < son: ans = 0
    elif son > 0:
        ans *= permutation(K-2, son, fact, revfact, mod)
        ans %= mod
    return ans
    

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    edge = [[] for i 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)
    mod = 7 + 10 ** 9

    fact = [1] * (K + 1)
    for i in range(2, K+1):
        fact[i] = (i * fact[i-1]) % mod
    revfact = [1] * (K+1)
    revfact[K] = pow(fact[K], mod - 2, mod)
    for i in reversed(range(1, K)):
        revfact[i] = ((i+1) * revfact[i+1]) % mod

    ans = K
    son = 0
    for next in edge[0]:
        son += 1
        ans *= dfs(next, 0, edge, mod, K, fact, revfact)
        ans %= mod
    ans *= permutation(K-1, son, fact, revfact, mod)
    ans %= mod

    print(ans)
    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

n, k = map(int, input().split())
ab = [list(map(lambda x:int(x)-1, input().split())) for _ in range(n-1)]

mod = 10**9+7

def dfs(K, graph, now, src):
    if src == -1:
        use_num_color = k-1
    else:
        use_num_color = k-2

    if len(graph[now])>k:
        return 0
    
    num_cases = 1
    for e in graph[now]:
        if e==src: continue
        num_cases *= use_num_color
        num_cases %= mod
        use_num_color -= 1

    for e in graph[now]:
        if e==src: continue
        num_cases *= dfs(K, graph, e, now)
        num_cases %= mod

    return num_cases

def make_graph(list):
    n = len(list)
    graph = [[] for _ in range(n+1)]
    for a, b in list:
        graph[a].append(b)
        graph[b].append(a)
    return graph

graph = make_graph(ab)
ans = k*dfs(k, graph, 0, -1)
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())
    a-=1;b-=1
    G[a].append(b)
    G[b].append(a)

rnk=[0 for i in range(N)]
reached=[0 for i in range(N)]
q=deque([0])
while(len(q)>0):
	r=q.popleft()
	reached[r]=1
	for p in G[r]:
		if reached[p]==1:
			continue
		rnk[p]=rnk[r]+1
		q.append(p)

reached=[0 for i in range(N)]
q=deque([0])
dp=[-1 for i in range(N)]
dp[0]=K
while(len(q)>0):
	r=q.popleft()
	reached[r]=1
	index=1
	if rnk[r]>0:
		index=2
	for p in G[r]:
		if reached[p]==1:
			continue
		dp[p]=K-index
		index+=1
		q.append(p)

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

Solution (Python):
import sys

sys.setrecursionlimit(10**9)


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

def dfs(K, graph, now, source):
  if source == -1:
    can_use_color_num = K - 1
  else:
    can_use_color_num = K - 2
  if len(graph[now]) > K:
    return 0
  else:
    case_num = 1
    for dst in graph[now]:
      if dst == source:
        continue
      case_num *= can_use_color_num
      can_use_color_num -= 1
      case_num %= mod
    for dst in graph[now]:
      if dst == source:
        continue
      case_num *= dfs(K, graph, dst, now)
      case_num %= mod
    return case_num
  

graph = [[] for i in range(N)]
for i in range(N - 1):
  a, b = map(lambda x:int(x)-1, input().split())
  graph[a].append(b)
  graph[b].append(a)

answer = K * dfs(K, graph, 0, -1)
answer %= mod
print(answer)

Solution (Python):
from collections import defaultdict, deque
n, k = list(map(int, input().split()))
color = [-1 for i in range(n+1)]
MOD = 10**9+7

graph = defaultdict(list)
for i in range(n-1):
  a, b = list(map(int, input().split()))
  graph[a].append(b)
  graph[b].append(a)

def bfs():
  que = deque([(1, 0, 0)])
  while len(que):
    x, par, sib = que.popleft()
    color[x] = k-min(2, par)-sib

    sib = 0
    for nx in graph[x]:
      if color[nx]==-1:
        que.append((nx, par+1, sib))
        sib += 1

bfs()
ans = 1
for i in range(1, n+1):
  ans = (ans*color[i])%MOD
print(ans)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
mod = 10**9+7
def dfs():
    stack = deque([[-1,0]])
    visited = set()
    case_num=1
    while stack:
        fr,n = stack.pop()
        if(n in visited):continue
        visited.add(n)
        color = 0
        if(fr==-1):
            color = K-1
        else:
            color = K-2
        if(K<len(edges[n])):
            return 0
        else:
            for e in edges[n]:
                if(e==fr):continue
                case_num*=color
                color-=1
                stack.append([n,e])
                case_num%=mod
    return case_num%mod

if(__name__=='__main__'):
    N,K = [int(x) for x in input().split()]
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        s,d = [int(x) for x in input().split()]
        edges[s-1].append(d-1)
        edges[d-1].append(s-1)
    ans = K*dfs()
    print(ans%mod)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
mod = 10**9+7
def dfs():
    stack = deque([[-1,0]])
    visited = set()
    case_num=1
    while stack:
        fr,n = stack.pop()
        if(n in visited):continue
        visited.add(n)
        color = 0
        if(fr==-1):
            color = K-1
        else:
            color = K-2
        if(K<len(edges[n])):
            return 0
        else:
            for e in edges[n]:
                if(e==fr):continue
                case_num*=color
                color-=1
                stack.append([n,e])
                case_num%=mod
    return case_num%mod

if(__name__=='__main__'):
    N,K = [int(x) for x in input().split()]
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        s,d = [int(x) for x in input().split()]
        edges[s-1].append(d-1)
        edges[d-1].append(s-1)
    ans = K*dfs()
    print(ans%mod)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

def perm(n, k):
    if n < 0:
        return 0
    if k > n:
        return 0
    return fact[n] * ifact[n-k] % mod

def dfs(v, p):
    global ans
    for nv in link[v]:
        if nv == p:
            continue
        dfs(nv, v)
    
    
    
    
    if p == -1:
        n = K
    else:
        n = K - 2
    if p == -1:
        k = len(link[v]) + 1
    else:
        k = len(link[v]) - 1

    ans *= perm(n, k)
    ans %= mod

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

mod = 10 ** 9 + 7
ans = 1

fact = [0] * (10**5+1)
fact[0] = 1
fact[1] = 1
for i in range(2, 10**5+1):
    fact[i] = fact[i-1] * i
    fact[i] %= mod
ifact = [0] * (10**5+1)
for i in range(10**5+1):
    ifact[i] = pow(fact[i], mod-2, mod)
    ifact[i] %= mod

dfs(0, -1)

print(ans % mod)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

def perm(n, k):
    if k > n:
        return 0
    return fact[n] * ifact[n-k] % mod

def dfs(v, p):
    global ans
    for nv in link[v]:
        if nv == p:
            continue
        dfs(nv, v)
    
    
    
    
    if p == -1:
        n = K
    else:
        n = K - 2
    if p == -1:
        k = len(link[v]) + 1
    else:
        k = len(link[v]) - 1

    ans *= perm(n, k)
    ans %= mod

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

mod = 10 ** 9 + 7
ans = 1

fact = [0] * (10**5+1)
fact[0] = 1
fact[1] = 1
for i in range(2, 10**5+1):
    fact[i] = fact[i-1] * i
    fact[i] %= mod
ifact = [0] * (10**5+1)
for i in range(10**5+1):
    ifact[i] = pow(fact[i], mod-2, mod)
    ifact[i] %= mod

dfs(0, -1)

print(ans % mod)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

def perm(n, k):
    if n < 0:
        return 0
    if k > n:
        return 0
    return fact[n] * ifact[n-k] % mod

def dfs(v, p):
    global ans
    for nv in link[v]:
        if nv == p:
            continue
        dfs(nv, v)
    
    
    
    
    if p == -1:
        n = K
    else:
        n = K - 2
    if p == -1:
        k = len(link[v]) + 1
    else:
        k = len(link[v]) - 1

    ans *= perm(n, k)
    ans %= mod

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

mod = 10 ** 9 + 7
ans = 1

fact = [0] * (10**5+1)
fact[0] = 1
fact[1] = 1
for i in range(2, 10**5+1):
    fact[i] = fact[i-1] * i
    fact[i] %= mod
ifact = [0] * (10**5+1)
for i in range(10**5+1):
    ifact[i] = pow(fact[i], mod-2, mod)
    ifact[i] %= mod

dfs(0, -1)

print(ans % mod)

Solution (Python):
import sys
from collections import deque

def main():
  input = sys.stdin.readline
  n,k = map(int,input().split())
  sl = [0]*(n+1)
  tree = [[] for i in range(n+1)]
  mod = 10**9+7
  ans = k

  for i in range(n-1):
    a,b = map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)
    
  lent = len(tree[1])
  if lent > 0:
    q = deque(tree[1])
    for x in range(k-1, k-1-lent, -1):
      ans = ans * x % mod
    sl[1] = 1
  else:
    print(k)
    exit()
  
  qpop = q.popleft
  qappend = q.append
  
  while q:
    pos = qpop()
    sl[pos] = 1
    lent = len(tree[pos]) - 1
    if lent > 0:
      for x in range(k-2, k-2-lent, -1):
        ans = ans * x % mod
    for i in tree[pos]:
      if sl[i] == 0:
        qappend(i)
  print(ans)

if __name__ == '__main__':
    main()

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

def main():
  n,k = map(int,input().split())
  sl = [0]*n
  tree = [[] for i in range(n)]
  mod = 10**9+7
  q = []
  ans = k

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

  if len(tree[0]) > 0:
    q = tree[0]
    for x in range(k-1, k-1-len(tree[0]), -1):
      ans = ans * x % mod
    sl[0] = 1
  else:
    print(k)
    exit()
  
  while q:
    pos = q.pop(0)
    sl[pos] = 1
    lent = len(tree[pos]) - 1
    if lent > 0:
      for x in range(k-2, k-2-lent, -1):
        ans = ans * x % mod
    for i in tree[pos]:
      if sl[i] == 0:
        q.append(i)
  print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
n,k,*t=map(int,open(0).read().split());c,e=k,[0]*-~n
for v in t:e[v]+=1;c=c*(k-e[v])**(e[v]>(v>1))%(10**9+7)
print(c)

Solution (Python):
n,k,*t=map(int,open(0).read().split());c,e=k,[0]*-~n
for v in t:
 e[v]+=1
 if(v>1)-e[v]:c=c*(k-e[v])%(10**9+7)
print(c)

Solution (Python):
def main():
  n,k,*t=map(int,open(0).read().split())
  c,e=k,[0]*(n+1)
  for v in t:
    e[v]+=1
    if(v>1)-e[v]:
      c=c*(k-e[v])%(10**9+7)
  print(c)
main()

Solution (Python):
n,k,*t=map(int,open(0).read().split());c,e=k,[0]*-~n
for v in t:
 e[v]+=1
 if(v>1)-e[v]:c=c*(k-e[v])%(10**9+7)
print(c)

Solution (Python):
n,k,*t=map(int,open(0).read().split());c,e=k,[0]*2**17
for v in t:
 e[v]+=1
 if(v>1)-e[v]:c=c*(k-e[v])%(10**9+7)
print(c)

Solution (Python):
n,k,*t=map(int,open(0).read().split())
c,e=k,[0]*2**17
for v in t:
  if(v<2)+e[v]:c=c*(k-e[v]-1)%(10**9+7)
  e[v]+=1
print(c)

Solution (Python):
def main():
  n,k,*t=map(int,open(0).read().split())
  e=tuple(set()for _ in[0]*n)
  for a,b in zip(t[::2],t[1::2]):
    e[a-1].add(b-1)
    e[b-1].add(a-1)
  c,q=k,[0]
  M=10**9+7
  while q:
    v,i=q.pop(),1
    for w in e[v]:
      c*=k-i-(v>0)
      c%=M
      e[w].remove(v)
      q+=w,
      i+=1
  print(c)
main()

Solution (Python):
def main():
  from collections import deque
  n,k,*t=map(int,open(0).read().split())
  e=tuple(set()for _ in[0]*n)
  for a,b in zip(t[::2],t[1::2]):
    e[a-1].add(b-1)
    e[b-1].add(a-1)
  c,q=k,deque([0])
  while q:
    v,i=q.pop(),1
    for w in e[v]:
      c=c*(k-i-(v>0))%(10**9+7)
      e[w].remove(v)
      q+=w,
      i+=1
  print(c)
main()

Solution (Python):
def main():
  n,k,*t=map(int,open(0).read().split())
  e=tuple(set()for _ in[0]*n)
  for a,b in zip(t[::2],t[1::2]):
    e[a-1].add(b-1)
    e[b-1].add(a-1)
  c,q=k,[0]
  while q:
    v,i=q.pop(),1
    for w in e[v]:
      c=c*(k-i-(v>0))%(10**9+7)
      e[w].remove(v)
      q+=[w]
      i+=1
  print(c)
main()

Solution (Python):
def main():
  n,k,*t=map(int,open(0).read().split())
  e=tuple(set()for _ in[0]*n)
  for a,b in zip(t[::2],t[1::2]):
    e[a-1].add(b-1)
    e[b-1].add(a-1)
  c,q=k,[0]
  while q:
    v,i=q.pop(),1
    for w in e[v]:
      c=c*(k-i-(v>0))%(10**9+7)
      e[w].remove(v)
      q.append(w)
      i+=1
  print(c)
main()

Solution (Python):
def main():
  n,k,*t=map(int,open(0).read().split())
  e=tuple(set()for _ in[0]*n)
  for a,b in zip(t[::2],t[1::2]):
    e[a-1].add(b-1)
    e[b-1].add(a-1)
  c,q=k,[0]
  while q:
    v,i=q.pop(),1
    for w in e[v]:
      c=c*(k-i-(v>0))%(10**9+7)
      e[w].remove(v)
      q+=w,
      i+=1
  print(c)
main()

Solution (Python):
def main():
  n,k,*t=map(int,open(0).read().split())
  e=tuple(set()for _ in[0]*n)
  for a,b in zip(t[::2],t[1::2]):
    e[a-1].add(b-1)
    e[b-1].add(a-1)
  c,q=k,[0]
  while q:
    v,i=q.pop(),1
    for w in e[v]:
      c=c*(k-i-(v>0))%(10**9+7)
      e[w].discard(v)
      q+=w,
      i+=1
  print(c)
main()

Solution (Python):
def main():
  n,k,*t=map(int,open(0).read().split())
  e=[set()for _ in[0]*n]
  for a,b in zip(t[::2],t[1::2]):
    e[a-1]|={b-1}
    e[b-1]|={a-1}
  c,q=k,[0]
  e=tuple(e)
  while q:
    v,i=q.pop(),1
    for w in e[v]:
      c=c*(k-i-(v>0))%(10**9+7)
      e[w].discard(v)
      q+=w,
      i+=1
  print(c)
main()

Solution (Python):
def main():
  n,k,*t=map(int,open(0).read().split())
  e=[set()for _ in[0]*n]
  for a,b in zip(t[::2],t[1::2]):
    e[a-1]|={b-1}
    e[b-1]|={a-1}
  c,q=k,[0]
  while q:
    v,i=q.pop(),1
    for w in e[v]:
      c=c*(k-i-(v>0))%(10**9+7)
      e[w].discard(v)
      q+=w,
      i+=1
  print(c)
main()

Solution (Python):
def main():
  n,k,*t=map(int,open(0).read().split())
  e=[set()for _ in[0]*n]
  for a,b in zip(t[::2],t[1::2]):
    e[a-1]|={b-1}
    e[b-1]|={a-1}
  c,q=k,[0]
  while q:
    v=q.pop()
    for i,w in enumerate(e[v],1):
      c=c*(k-i-(v>0))%(10**9+7)
      e[w]-={v}
      q+=w,
  print(c)
main()

Solution (Python):
def main():
  n,k,*t=map(int,open(0).read().split())
  e=[set()for _ in[0]*n]
  for a,b in zip(t[::2],t[1::2]):
    e[a-1].add(b-1)
    e[b-1].add(a-1)
  c,q=k,[0]
  while q:
    v,i=q.pop(),1
    for w in e[v]:
      c=c*(k-i-(v>0))%(10**9+7)
      e[w]-={v}
      q+=w,
      i+=1
  print(c)
main()

Solution (Python):
def main():
  n,k,*t=map(int,open(0).read().split())
  e=[set()for _ in[0]*n]
  for a,b in zip(t[::2],t[1::2]):
    e[a-1]|={b-1}
    e[b-1]|={a-1}
  c,q=k,[0]
  while q:
    v,i=q.pop(),1
    for w in e[v]:
      c=c*(k-i-(v>0))%(10**9+7)
      e[w]-={v}
      q.append(w)
      i+=1
  print(c)
main()

Solution (Python):
def main():
  from collections import deque
  n,k,*t=map(int,open(0).read().split())
  e=[set()for _ in[0]*n]
  for a,b in zip(t[::2],t[1::2]):
    e[a-1]|={b-1}
    e[b-1]|={a-1}
  c,q=k,deque([0])
  while q:
    v,i=q.pop(),1
    for w in e[v]:
      c=c*(k-i-(v>0))%(10**9+7)
      e[w]-={v}
      q.append(w)
      i+=1
  print(c)
main()

Solution (Python):
def main():
  n,k,*t=map(int,open(0).read().split())
  e=[set()for _ in[0]*n]
  for a,b in zip(t[::2],t[1::2]):
    e[a-1]|={b-1}
    e[b-1]|={a-1}
  c,q=k,[0]
  while q:
    v,i=q.pop(),1
    for w in e[v]:
      c=c*(k-i-(v>0))%(10**9+7)
      e[w]-={v}
      q+=w,
      i+=1
  print(c)
main()

Solution (Python):
n,k,*t=map(int,open(0).read().split())
e=[set()for _ in[0]*n]
for a,b in zip(t[::2],t[1::2]):
  e[a-1]|={b-1}
  e[b-1]|={a-1}
c,q=k,[0]
while q:
  v,i=q.pop(),1
  for w in e[v]:
    c=c*(k-i-(v>0))%(10**9+7)
    e[w]-={v}
    q+=w,
    i+=1
print(c)

Solution (Python):
n,k,*t=map(int,open(0).read().split())
e=[set()for _ in[0]*n]
for a,b in zip(t[::2],t[1::2]):
  e[a-1]|={b-1}
  e[b-1]|={a-1}
c,q=k,[0]
while q:
  v,i=q.pop(),1
  for w in e[v]:
    c=c*(k-i-(v>0))%(10**9+7)
    e[w]-={v}
    q+=w,
    i+=1
print(c)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def dfs(v,c):
  i=1
  for w in e[v]:
    e[w]-={v}
    c=c*dfs(w,k-i-(v>0))%(10**9+7)
    i+=1
  return c
n,k,*t=map(int,open(0).read().split())
e=[set()for _ in[0]*n]
for a,b in zip(t[::2],t[1::2]):
  e[a-1]|={b-1}
  e[b-1]|={a-1}
print(dfs(0,k))

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def dfs(v,c):
  for i,w in enumerate(e[v]):
    e[w]-={v}
    c=c*dfs(w,k-i+~(v>0))%(10**9+7)
  return c
n,k,*t=map(int,open(0).read().split())
e=[set()for _ in[0]*n]
for a,b in zip(t[::2],t[1::2]):
  e[a-1]|={b-1}
  e[b-1]|={a-1}
print(dfs(0,k))

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def dfs(v,c):
  for i,w in enumerate(e[v]):
    e[w].discard(v)
    c=c*dfs(w,k-i+~(v>0))%(10**9+7)
  return c
n,k,*t=map(int,open(0).read().split())
e=eval('set(),'*n)
for a,b in zip(t[::2],t[1::2]):
  e[a-1].add(b-1)
  e[b-1].add(a-1)
print(dfs(0,k))

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def dfs(v,c):
  for i,w in enumerate(e[v]):
    e[w].discard(v)
    c=c*dfs(w,k-i+~(v>0))%(10**9+7)
  return c
n,k,*t=map(int,open(0).read().split())
e=eval('set(),'*n)
for a,b in zip(t[::2],t[1::2]):
  e[a-1].add(b-1)
  e[b-1].add(a-1)
print(dfs(0,k))

Solution (Python):


import sys

sys.setrecursionlimit(10**7)


def read_h(typ=int):
    return list(map(typ, input().split()))


def read_v(n, m=1, typ=int):
    return [read_h() if m > 1 else typ(input()) for _ in range(n)]


MOD = 10**9 + 7


def dfs(colors, graph, parent, current):
    if colors < len(graph[current]):
        return 0

    num_avail_colors = colors - 1 if parent < 0 else colors - 2
    num_cases = 1
    neighbors = graph[current]
    for neighbor in neighbors:
        if neighbor == parent:
            continue

        num_cases *= num_avail_colors
        num_avail_colors -= 1
        num_cases %= MOD

    for neighbor in neighbors:
        if neighbor == parent:
            continue

        num_cases *= dfs(colors, graph, current, neighbor)
        num_cases %= MOD

    return num_cases


def main():
    N, K = read_h()
    graph = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = read_h()
        graph[a - 1].append(b - 1)
        graph[b - 1].append(a - 1)

    ans = K * dfs(K, graph, -1, 0) % MOD
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
MOD = 10 ** 9 + 7
def LI(): return map(int, sys.stdin.readline().split())

def main():
    n, k = LI()
    g = [[] for i in range(n+1)]
    for i in range(n-1):
        a, b = LI()
        g[a].append(b)
        g[b].append(a)

    Q = deque([1])
    ans = k
    Qappend = Q.append
    searched = [0] * (n+1)
    searched[1] = 1
    Qp = Q.popleft
    cand = k - 1
    while len(Q) != 0:
        v = Qp()
        for i in g[v]:
            if searched[i] == 1:
                continue
            searched[i] = 1
            ans = ans * cand % MOD
            cand = cand - 1
            Qappend(i)
        cand = k - 2
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque
MOD = 10 ** 9 + 7
def LI(): return map(int, sys.stdin.readline().split())

def main():
    n, k = LI()
    g = [[] for i in range(n+1)]
    for i in range(n-1):
        a, b = LI()
        g[a].append(b)
        g[b].append(a)

    Q = deque([1])
    ans = k
    Qappend = Q.append
    searched = [0] * (n+1)
    searched[1] = 1
    Qp = Q.popleft
    cand = k - 1
    while len(Q) != 0:
        v = Qp()
        for i in g[v]:
            if searched[i] == 1:
                continue
            searched[i] = 1
            ans = ans * cand % MOD
            cand = cand - 1
            Qappend(i)
        cand = k - 2
    print(ans)

if __name__ == "__main__":
    main()

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

from collections import defaultdict

v = defaultdict(set)

for a, b in AB:
    v[a].add(b)
    v[b].add(a)

M = 10**9+7

import sys
sys.setrecursionlimit(100001)

result = 1

def check(n, b, p):
    global result
    result = result * max(K - b - p, 0) % M
    
    np = min(p + 1, 2)
    for b, x in enumerate(v[n]):
        v[x].remove(n)
        check(x, b, np)

check(1, 0, 0)

print(result)

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

def main():
  
  n,k = map(int,input().split())
  sl = [0]*(n+1)
  tree = [[] for i in range(n+1)]
  
  for i in range(n-1):
    a,b = map(int,input().split())
    tree[a] += (b,)
    tree[b] += (a,)

  def dfs(x,depth,k):
    sl[x] = 1
    child = 0
    ans = 1
    for i in tree[x]:
      if sl[i] == 0:
        ans *= dfs(i,depth+1,k)
        child += 1
    if depth == 0:
      for x in range(k-1, k-1-child, -1):
        ans = ans * x % mod   
    else:    
      for x in range(k-2, k-2-child, -1):
        ans = ans * x % mod
    ans %= mod
    return ans

  print(dfs(1,0,k)*k%mod)

if __name__ == '__main__':
    main()