#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N,K;
cin >> N >> K;
vector<vector<pair<int,int>>> adj(N+1);
for(int i=1;i<N;i++){
int u,v,c;cin>>u>>v>>c;u++;v++;
adj[u].emplace_back(v,c);
adj[v].emplace_back(u,c);
}
vector<int> ans(N+1);
vector DP(N+1,vector<int>(K+1));
vector<int> subsize(N+1);
{
function<void(int,int)> dfs = [&](int x,int p){
subsize[x]=1;
DP[x][K]=1;
for(auto&[v,c]:adj[x])if(v!=p){
dfs(v,x);
subsize[x]+=subsize[v];
for(int i=c;i<=K;i++){
DP[x][i-c]+=DP[v][i];
}
for(int i=0;i<c;i++){
DP[x][K-c]+=DP[v][i];
}
}
};
dfs(1,-1);
}
{
function<void(int,int)> dfs = [&](int x,int p){
int pedge = -1;
for(auto&[v,c]:adj[x])if(v==p)pedge=c;
if(p!=-1){
subsize[x]+=subsize[p];
for(int i=pedge;i<=K;i++){
DP[x][i-pedge]+=DP[p][i];
}
for(int i=0;i<pedge;i++){
DP[x][K-pedge]+=DP[p][i];
}
}
for(auto&[v,c]:adj[x]){
subsize[x]-=subsize[v];
for(int i=c;i<=K;i++){
DP[x][i-c]-=DP[v][i];
}
for(int i=0;i<c;i++){
DP[x][K-c]-=DP[v][i];
}
for(int i=0;i<c;i++){
ans[x]+=DP[x][i]*subsize[v];
}
if(v!=p)dfs(v,x);
subsize[x]+=subsize[v];
for(int i=c;i<=K;i++){
DP[x][i-c]+=DP[v][i];
}
for(int i=0;i<c;i++){
DP[x][K-c]+=DP[v][i];
}
}
if(p!=-1){
subsize[x]-=subsize[p];
for(int i=pedge;i<=K;i++){
DP[x][i-pedge]-=DP[p][i];
}
for(int i=0;i<pedge;i++){
DP[x][K-pedge]-=DP[p][i];
}
}
};
dfs(1,-1);
}
for(int i=1;i<=N;i++)cout<<ans[i]<<'\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |