#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=5e4+3,M=153,P=10007;
int n,m,x,y,o,K,jc[M],fto[M],head[N],S[M][M],f[N][M],g[N][M];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int dp=0;x=0;char c=getchar();
while(c<'0'||c>'9')dp|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=dp?-x:x;
}
inline void dfs1(Re x,Re fa){
f[x][0]=1;
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa){
dfs1(to,x),(f[x][0]+=f[to][0])%=P;
for(Re j=1;j<=K;++j)(f[x][j]+=(f[to][j]+f[to][j-1])%P)%=P;
}
}
inline void dfs2(Re x,Re fa){
if(fa){
fto[0]=(g[fa][0]+f[fa][0]-f[x][0]+P)%P;
for(Re j=1;j<=K;++j)fto[j]=(g[fa][j]+f[fa][j]-(f[x][j]+f[x][j-1])%P+P)%P;
g[x][0]=fto[0];
for(Re j=1;j<=K;++j)g[x][j]=(fto[j]+fto[j-1])%P;
}
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa)dfs2(to,x);
}
inline void Stirling(Re N){
for(Re i=0;i<=N;++i)S[i][i]=1;
for(Re i=1;i<=N;++i)
for(Re j=1;j<i;++j)
S[j][i]=(S[j-1][i-1]+j*S[j][i-1]%P)%P;
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(K),m=n-1;
while(m--)in(x),in(y),add(x,y),add(y,x);
dfs1(1,0),dfs2(1,0),Stirling(K),jc[0]=1;
for(Re i=1;i<=K;++i)jc[i]=jc[i-1]*i%P;
for(Re i=1;i<=n;++i){
Re ans=0;
for(Re j=0;j<=K;++j)
(ans+=S[j][K]*jc[j]%P*(f[i][j]+g[i][j])%P)%=P;
printf("%d\n",ans);
}
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const LL N=1e5+3,inf=1e18;
int n,m,x,y,z,o,A[N],S[N],dis[N],size[N],head[N];LL ans=inf,f[N],g[N];
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void dfs1(Re x,Re fa){
size[x]=1,S[x]=A[x];
for(Re i=head[x],to;i;i=a[i].next)if((to=a[i].to)!=fa)
dis[to]=a[i].w,dfs1(to,x),S[x]+=S[to],size[x]+=size[to],f[x]+=f[to]+(LL)S[to]*a[i].w;
}
inline void dfs2(Re x,Re fa){
if(fa)g[x]=g[fa]+f[fa]-f[x]-(LL)S[x]*dis[x]+(LL)(S[1]-S[x])*dis[x];
for(Re i=head[x],to;i;i=a[i].next)if((to=a[i].to)!=fa)dfs2(to,x);
ans=min(ans,f[x]+g[x]);
}
int main(){
// freopen("123.txt","r",stdin);
in(n),m=n-1;
for(Re i=1;i<=n;++i)in(A[i]);
while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
dfs1(1,0),dfs2(1,0),printf("%lld\n",ans);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define R register int
using namespace std;
int head[6010],a,b,t,i,j,n,f[6010][2],pan[6010];
struct QAQ{int next,to;}Q[6010];
inline void add(int x,int y){Q[++t].to=y,Q[t].next=head[x],head[x]=t;}
inline void dfs(int w){
for(R k=head[w];k;k=Q[k].next){
int to=Q[k].to;
dfs(to);
f[w][0]+=max(f[to][0],f[to][1]);
f[w][1]+=f[to][0];
}
}
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&f[i][1]);
for(i=1;i<n;i++)scanf("%d%d",&a,&b),pan[a]++,add(b,a);
for(i=1;i<=n;i++)
if(!pan[i]){
dfs(i);
printf("%d\n",max(f[i][0],f[i][1]));
return 0;
}
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define R register int
using namespace std;
struct QAQ{int to,next;}a[1505];
int m,pan[1505],n,t,w[1505],dp[1505][3],head[1505];
inline void add(int x,int y){a[++t].to=y,a[t].next=head[x],head[x]=t;}
//dp[i][0] 以及各种情况的具体转移方程和初始状态
inline void dfs(int x){
R i,to,dd=0xfffffff;
dp[x][1]=w[x];dp[x][2]=0;dp[x][0]=0;
for(i=head[x];i;i=a[i].next){
dfs(to=a[i].to);
dd=min(dd,dp[to][1]-min(dp[to][0],dp[to][1]));
dp[x][0]+=min(dp[to][0],dp[to][1]);
dp[x][1]+=min(dp[to][1],dp[to][2]);
dp[x][2]+=min(dp[to][0],dp[to][1]);
}
dp[x][0]+=dd;
}
int main(){
memset(dp,127,sizeof(dp));
scanf("%d",&n);
R i,j,a,k,r;
for(i=1;i<=n;i++){
scanf("%d%d%d",&a,&k,&m);w[a]=k;
for(j=1;j<=m;j++)scanf("%d",&r),pan[r]=1,add(a,r);
}
for(i=1;i<=n;i++)
if(!pan[i]){
dfs(i);
printf("%d",min(dp[i][1],dp[i][0]));
return 0;
}
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=5003,P=998244353;
int n,m,o,x,y,f[N],g[N],A[N],jc[N],head[N];char s[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline int mi(Re x,Re k){
Re s=1;
while(k){
if(k&1)s=(LL)s*x%P;
x=(LL)x*x%P,k>>=1;
}
return s;
}
inline int inv(Re x){return mi(x,P-2);}
int sz1[N],sz0[N],lim[N],dp[N][N],tmp[N];
inline void dfs0(Re x,Re fa){
sz0[x]=(!A[x]),sz1[x]=A[x];
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa)dfs0(to,x),sz1[x]+=sz1[to],sz0[x]+=sz0[to];
// lim[x]=min(sz1[x],size[x]-sz1[x]);
}
inline void dfs(Re x,Re fa){
dp[x][0]=1;
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa){
dfs(to,x);
for(Re j=0;j<=lim[x]+lim[to];++j)tmp[j]=0;
for(Re j=lim[x];j>=0;--j)
for(Re k=lim[to];k>=0;--k)
(tmp[j+k]+=(LL)dp[x][j]*dp[to][k]%P)%=P;
lim[x]+=lim[to];
for(Re j=0;j<=lim[x];++j)dp[x][j]=tmp[j];
}
++lim[x];
if(A[x])for(Re j=min(lim[x],sz0[x]);j>=1;--j)
(dp[x][j]+=(LL)dp[x][j-1]*(sz0[x]-(j-1))%P)%=P;
else for(Re j=min(lim[x],sz1[x]);j>=1;--j)
(dp[x][j]+=(LL)dp[x][j-1]*(sz1[x]-(j-1))%P)%=P;
while(!dp[x][lim[x]])--lim[x];
}
inline int C(Re m,Re n){return (LL)jc[n]*inv(jc[m])%P*inv(jc[n-m])%P;}
int main(){
// freopen("match.in","r",stdin);
// freopen("match.out","w",stdout);
in(n),scanf("%s",s+1),m=n-1,jc[0]=1;
for(Re i=1;i<=n;++i)A[i]=s[i]-'0',jc[i]=(LL)jc[i-1]*i%P;
while(m--)in(x),in(y),add(x,y),add(y,x);
dfs0(1,0),dfs(1,0);
// for(Re i=1;i<=n;++i)printf("lim[%d]=%d\n",i,lim[i]);
// for(Re i=0;i<=n/2;++i)printf("dp[%d]=%d\n",i,dp[1][i]);
// for(Re j=0;j<=lim[1];++j)printf("%d ",dp[1][j]);
for(Re j=0;j<=lim[1];++j)g[j]=(LL)dp[1][j]*jc[n/2-j]%P;
for(Re i=lim[1];i>=0;--i){
f[i]=g[i];
for(Re j=i+1;j<=lim[1];++j)f[i]=(f[i]-(LL)C(i,j)*f[j]%P+P)%P;
}
for(Re i=0;i<=n/2;++i)printf("%d\n",f[i]);
fclose(stdin);
fclose(stdout);
return 0;
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=2003;
int n,m,x,y,z,o,K,size[N],head[N];LL tmp[N],dp[N][N];
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void dfs(Re x,Re fa){
size[x]=1,dp[x][0]=dp[x][1]=0;
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa){
dfs(to,x);
for(Re j=0;j<=size[x]+size[to];++j)tmp[j]=dp[0][0];
for(Re j=size[x];j>=0;--j)
if(dp[x][j]>=0)for(Re k=size[to];k>=0;--k)
if(dp[to][k]>=0)
tmp[j+k]=max(tmp[j+k],dp[x][j]+dp[to][k]+
(LL)a[i].w*((LL)k*(K-k)+(LL)(size[to]-k)*(n-size[to]-(K-k)))
);
size[x]+=size[to];
for(Re j=0;j<=size[x];++j)dp[x][j]=tmp[j];
}
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(K),m=n-1;
while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
memset(dp,-20,sizeof(dp));
dfs(1,0),printf("%lld\n",dp[1][K]);
}