#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=70007;
ll n,m,k;
int sz[N];
vector<pair<int,ll>>g[N];
ll ans[N];
void calcsz(int v, int par){
sz[v]=1;
for(auto e:g[v]){
int to=e.ff;
if(to!=par){
calcsz(to,v);
sz[v]+=sz[to];
}
}
}
void dfs(int v, int par, ll cur){
// cout<<"TAZA DFS"<<endl;
for(auto e:g[v]){
int to=e.ff;
ll w=e.ss;
// cout<<"dfs: "<<v<<" "<<par<<" "<<cur<<endl;
// cout<<"edge: "<<to<<" "<<w<<endl;
if(to!=par){
if(cur+w>k){
// cout<<to<<" "<<cur<<endl;
ans[v]+=sz[to];
dfs(to,v,w);
}
else{
dfs(to,v,cur+w);
}
}
}
}
ll getdist(const vector<ll>& pf, int x, int y){
if(x==0)return pf[y-1];
return pf[y-1]-pf[x-1];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// freopen("Einput.txt","r",stdin);
// freopen("Eoutput.txt","w",stdout);
cin>>n>>k;
for(int i=0;i<n-1;i++){
int u,v;
ll w;
cin>>u>>v>>w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
if(n>=1000){
for(int v=0;v<n;v++){
// cout<<"root: "<<v<<endl;
calcsz(v,-1);
dfs(v,-1,0);
}
for(int v=0;v<n;v++){
cout<<ans[v]<<endl;
}
}
else{
vector<int>a;
vector<ll>p;
int root=0;
for(int v=0;v<n;v++){
if(g[v].size()==1){
root=v;
break;
}
}
a.push_back(root);
a.push_back(g[root][0].ff);
p.push_back(g[root][0].ss);
root=g[root][0].ff;
while(g[root].size()!=1){
if(g[root][0].ff!=a[a.size()-2]){
a.push_back(g[root][0].ff);
p.push_back(g[root][0].ss);
root=g[root][0].ff;
}
else{
a.push_back(g[root][1].ff);
p.push_back(g[root][1].ss);
root=g[root][1].ff;
}
}
vector<int>prev(a.size(),-1);
int l=a.size()-1;
ll sum=0;
for(int r=a.size()-1;r>=0;r--){
while(l>0&&sum<=k){
l--;
sum+=p[l];
}
if(sum>k)prev[r]=l+1;
sum-=p[r-1];
}
vector<int>nxt(a.size(),a.size());
l=0;
sum=0;
for(int r=0;r<a.size();r++){
while(l<a.size()-1&&sum<=k){
sum+=p[l];
l++;
}
if(sum>k)nxt[r]=l-1;
sum-=p[r];
}
vector<ll>ansnxt(a.size(),0);
for(int i=0;i<a.size();i++){
if(nxt[i]!=a.size()){
ansnxt[nxt[i]]+=ansnxt[i]+1;
}
ansnxt[i]*=(a.size()-i-1);
ans[a[i]]+=ansnxt[i];
}
vector<ll>ansprev(a.size(),0);
for(int i=a.size()-1;i>=0;i--){
if(prev[i]!=-1){
ansprev[prev[i]]+=ansprev[i]+1;
}
ansprev[i]*=i;
ans[a[i]]+=ansprev[i];
}
// for(int i=0;i<a.size();i++){
// cout<<i<<": "<<a[i]<<" "<<nxt[i]<<" "<<prev[i]<<" "<<ansnxt[i]<<" "<<ansprev[i]<<endl;
// }
for(int i=0;i<n;i++){
cout<<ans[i]<<endl;
}
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:121:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(int r=0;r<a.size();r++){
| ~^~~~~~~~~
Main.cpp:122:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | while(l<a.size()-1&&sum<=k){
| ~^~~~~~~~~~~
Main.cpp:130:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | for(int i=0;i<a.size();i++){
| ~^~~~~~~~~
Main.cpp:131:22: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | if(nxt[i]!=a.size()){
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1884 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1884 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1884 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2136 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1880 KB |
Output is correct |
| 2 |
Execution timed out |
3597 ms |
12020 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1884 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1884 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1880 KB |
Output is correct |
| 4 |
Execution timed out |
3597 ms |
12020 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1884 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1884 KB |
Output is correct |
| 3 |
Execution timed out |
3562 ms |
6584 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1884 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1884 KB |
Output is correct |
| 3 |
Execution timed out |
3562 ms |
6584 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1884 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1884 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2136 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
