# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1170842 | zyq181 | Petrol stations (CEOI24_stations) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#include <bits/stdc++.h>
using namespace std;
int N, K;
int inp1, inp2, inp3;
vector<pair<int, int> > adjList[70010];
int cnt;
int ans[70010];
int subtree[70010];
void dfs(int x, int p = -1, int left){
subtree[x] += 1;
for(auto it: adjList[x]){
if(p == it.first) continue;
if(left >= it.second){
dfs(it.first, x, left - it.second);
subtree[x] += subtree[it.first];
}
else{
dfs(it.first, x, K - it.second);
subtree[x] += subtree[it.first];
ans[x] += (subtree[it.first]);
}
}
}
int32_t main(){
cin >> N >> K;
for(int a=0; a<N-1; a++){
cin >> inp1 >> inp2 >> inp3;
adjList[inp1].push_back({inp2, inp3});
adjList[inp2].push_back({inp1, inp3});
}
int rt = 0;
for(int a=0; a<N; a++){
dfs(a, -1, K);
}
for(int a=0; a<N; a++) cout << ans[a] << '\n';
}