This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <list>
#include <unordered_set>
#include <unordered_map>
#include <math.h>
#include <bitset>
#include <cmath>
#include <vector>
#include <iomanip>
#include <random>
#include <chrono>
#include <cassert>
using namespace std;
#define ll long long
#define fr first
#define sc second
#define pb push_back
#define US freopen(".in", "r", stdin); freopen("j.out", "w", stdout);
ll gcd(ll a, ll b)
{
if (a == 0 || b == 0) {
return max(a, b);
}
if (a <= b) {
return gcd(a, b % a);
}
else {
return gcd(a % b, b);
}
}
ll lcm(ll a, ll b) {
return (a / gcd(a, b)) * b;
}
const int N = 70005;
const ll oo = 100000000000000000, MOD = 1000000007;
ll cnt[N];
int n, k, sz[N];
vector<pair<int, int>> g[N];
void dfs(int u, int p,int sm) {
//cout << u << endl;
for (int i = 0; i < g[u].size(); ++i) {
int h = g[u][i].fr;
int w = g[u][i].sc;
if (h != p) {
if (sm >= w) {
dfs(h, u, sm - w);
}
else {
cnt[u] += sz[h];
dfs(h, u, k-w);
}
}
}
}
void dfs1(int u, int p) {
for (int i = 0; i < g[u].size(); ++i) {
int h = g[u][i].fr;
if (h != p) {
dfs1(h, u);
sz[u] += sz[h];
}
}
++sz[u];
}
void solve() {
cin >> n >> k;
for (int i = 1; i <= n - 1; ++i) {
int u, v, w;
cin >> u >> v >> w;
g[u].pb({ v,w });
g[v].pb({ u,w });
}
for (int i = 0; i < n; ++i) {
//cout << i << endl;
for (int j = 0; j < n; ++j) {
sz[j] = 0;
}
dfs1(i, -1);
dfs(i, -1, k);
}
for (int i = 0; i < n; ++i) {
cout << cnt[i] << endl;
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
//US
int tt = 1;
//cin >> tt;
while (tt--) {
solve();
}
}
Compilation message (stderr)
Main.cpp: In function 'void dfs(int, int, int)':
Main.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for (int i = 0; i < g[u].size(); ++i) {
| ~~^~~~~~~~~~~~~
Main.cpp: In function 'void dfs1(int, int)':
Main.cpp:74:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for (int i = 0; i < g[u].size(); ++i) {
| ~~^~~~~~~~~~~~~
# | 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... |