Problem p02985 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10000000)

mod=int(1e9+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);
 
dp=[-1 for x in range(n)]
def f(v,p):
  if dp[v]!=-1:
    return dp[v]

  dp[v]=1
  j=1+int(v!=0)
  for i in g[v]:
    if i!=p:
      dp[v]=(dp[v]*f(i,v)*max(k-j,0))%mod
      j+=1
  return dp[v]
 
print(f(0,-1)*k%mod)

Buggy submission (verdict: Runtime Error):
mod=int(1e9+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);
 
dp=[-1 for x in range(n)]
def f(v,p):
  if dp[v]!=-1:
    return dp[v]

  dp[v]=1
  j=1+int(v!=0)
  for i in g[v]:
    if i!=p:
      dp[v]=(dp[v]*f(i,v)*max(k-j,0))%mod
      j+=1
  return dp[v]
 
print(f(0,-1)*k%mod)

Buggy submission (verdict: Runtime Error):
mod=int(1e9+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);
 
dp=[-1 for x in range(n)]
def f(v,p):
  if dp[v]!=-1:
    return dp[v]

  dp[v]=1
  j=1+int(v!=0)
  for i in g[v]:
    if i!=p:
      dp[v]=(dp[v]*f(i,v)*max(k-j,0))%mod
      j+=1
  return dp[v]
 
print(f(0,-1)*k%mod)

Buggy submission (verdict: Runtime Error):
mod=int(1e9+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);
 
dp=[-1 for x in range(n)]
def f(v,p):
  if dp[v]!=-1:
    return dp[v]

  dp[v]=1
  j=1+int(v!=0)
  for i in g[v]:
    if i!=p:
      dp[v]=(dp[v]*f(i,v)*max(k-j,0))%mod
      j+=1
  return dp[v]
 
print(f(0,-1)*k)

Buggy submission (verdict: Runtime Error):
#ifndef DEBUG 
	#pragma GCC optimize ("Ofast")
#endif
#include <bits/stdc++.h>
using namespace std;

#define hfor(var, s, e) for(int var=s; int(s)<=var && var<int(e); ++var)//half-opened range
#define hfori(var, s, e) for(int var=e-1; int(s)<=var && var<int(e); --var)//inversion
#define hforo(var, s, e) int var=s; for(; int(s)<=var && var<int(e); ++var)//out declaration
#define hforoi(var, s, e) int var=e-1; for(; int(s)<=var && var<int(e); --var)
#define cfor(var, s, e) hfor(var, s, (e)+1)//closed range
#define cfori(var, s, e) hfori(var, s, (e)+1)
#define cforo(var, s, e) hforo(var, s, (e)+1)
#define cforoi(var, s, e) hforoi(var, s, (e)+1)
#define rep(x) hfor(repi,0,x)
#define all(x) x.begin(),x.end()
#define sum_in(s,e) accumulate(s,e,0ll)
#define mri(it) make_reverse_iterator(it)//*mri(it) == *prev(it)
#define gcd __gcd
template<typename C, typename RI> RI rerase(C& c, RI ri){return next(mri(c.erase(prev(ri.base()))));}
template<typename T> constexpr T inf() { return numeric_limits<T>::max() / 2; }
using f64 = double;using i64=long long;using u64=unsigned long long;
const f64 pi=acos(-1), eps=1e-12;
const int prime=998244353;//1073741783 int(2e9+11) int(1e9+9)
const int mod=int(1e9+7);

auto _dummy=(ios::sync_with_stdio(0), cin.tie(0), cout.tie(0),
(cout<<fixed<<setprecision(11)), srand((int)time(0)), 0);
#define endl '\n'//not interactive?
#define int i64//overflow?

int n, k;
vector<int> g[100000];
bool vis[100000];

int f(int v, int p){
	vis[v]=true;
	
	int s=0;
	if(p>=0)
		for(auto i:g[p])
			s+=vis[i];
	int ret=max(k-s, 0ll);
	for(auto i:g[v])
		if(i!=p)
			ret=(ret*f(i,v))%mod;
	return ret;
}

signed main(){
	cin>>n>>k;
	hfor(i,0,n-1){
		int a,b;
		cin>>a>>b;
		a--,b--;
		g[a].push_back(b), g[b].push_back(a);
	}
	cout<<f(0,-1)<<endl;
	
	return 0;
}

/*mod=int(1e9+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);
 
dp=[-1 for x in range(n)]
def f(v,p):
  if dp[v]!=-1:
    return dp[v]
  dp[v]=0

  s=0
  if p>=0:
    for i in g[p]:
      s += 1 if dp[i]!=-1 else 0
 
  dp[v]=max(k-s,0)
  for i in g[v]:
    if i!=p:
      dp[v]=(dp[v]*f(i,v))%mod
  return dp[v]
 
print(f(0,-1))*/

Buggy submission (verdict: Runtime Error):
mod=int(1e9+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);
 
dp=[-1 for x in range(n)]
def f(v,p):
  if dp[v]!=-1:
    return dp[v]
  dp[v]=0

  s=0
  if p>=0:
    for i in g[p]:
      s += 1 if dp[i]!=-1 else 0
 
  dp[v]=max(k-s,0)
  for i in g[v]:
    if i!=p:
      dp[v]=(dp[v]*f(i,v))%mod
  return dp[v]
 
print(f(0,-1))

Buggy submission (verdict: Runtime Error):
mod=int(1e9+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);
 
dp=[-1 for x in range(n)]
def f(v,p):
  if dp[v]!=-1:
    return dp[v]
  dp[v]=0

  s=0
  if p>=0:
    for i in g[p]:
      s += 1 if dp[i]!=-1 else 0
 
  dp[v]=max(k-s,0)
  for i in g[v]:
    if i!=p:
      dp[v]=(dp[v]*f(i,v))%mod
  return dp[v]
 
print(f(0,-1))

Buggy submission (verdict: Runtime Error):
mod=int(1e9+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);
 
dp=[-1 for x in range(n)]
def f(v,p):
  if dp[v]!=-1:
    return dp[v]
  dp[v]=0

  s=0
  if p>=0:
    for i in g[p]:
      s += 1 if dp[v]!=-1 else 0
 
  dp[v]=max(k-s,0)
  for i in g[v]:
    if i!=p:
      dp[v]=(dp[v]*f(i,v))%mod
  return dp[v]
 
print(f(0,-1))

Buggy submission (verdict: Runtime Error):
mod=int(1e9+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);

dp=[-1 for x in range(n)]
def f(v,p):
  if dp[v]!=-1:
    return dp[v]
  
  s=0
  if p>=0:
    s=len(g[p])

  dp[v]=max(k-s,0)
  for i in g[v]:
    if i!=p:
      dp[v]=(dp[v]*f(i,v))%mod
  return dp[v]

print(f(0,-1))