#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef vector<char> VC;
typedef vector<VC> VVC;
typedef vector<bool> VB;
typedef vector<VB> VVB;
namespace TLE {
int n, k;
VVPI gp;
VL ans;
VI sub;
void dfs(int u, int p, int fuel) {
sub[u] = 1;
for (auto[v, w] : gp[u]) if (v != p) {
bool need = false;
int f = fuel-w;
if (f < 0) {
f = k-w;
need = true;
}
dfs(v, u, f);
sub[u] += sub[v];
if (need) ans[u] += sub[v];
}
}
VL solve(VVPI GP_ARG, int K_ARG) {
gp = GP_ARG;
k = K_ARG;
n = gp.size();
ans = VL(n);
sub = VI(n);
rep(u, n) {
/*ans = VL(n);*/
dfs(u, -1, k);
/*for (int x : ans) cout << x << " "; cout << endl;*/
}
return ans;
}
};
int n, k;
VVPI gp;
VVL dp;
VI sbt;
void addnode(int u, int v, int w) {
replr(j, 0, k) {
if (j < w) dp[u][k-w] += dp[v][j];
else dp[u][j-w] += dp[v][j];
}
}
void remnode(int u, int v, int w) {
replr(j, 0, k) {
if (j < w) dp[u][k-w] -= dp[v][j];
else dp[u][j-w] -= dp[v][j];
}
}
VL ans;
void dfs(int u = 0, int p = -1) {
sbt[u] = 1;
dp[u][k]++;
for (auto[v, w] : gp[u]) if (v != p) {
dfs(v, u);
addnode(u, v, w);
sbt[u] += sbt[v];
ll contr = 0;
rep(j, w) contr += dp[v][j];
ans[v] += contr * (n-sbt[v]);
/*cout << "PROCESSING EDGE " << v << " " << u << ": " << contr << " * " << (n-sbt[v]) << endl;*/
}
}
void reroot(int u = 0, int p = -1) {
for (auto[v, w] : gp[u]) if (v != p) {
remnode(u, v, w);
addnode(v, u, w);
ll contr = 0;
rep(j, w) contr += dp[u][j];
ans[u] += contr * (sbt[v]);
/*cout << "PROCESSING EDGE " << u << " " << v << ": " << contr << " * " << (sbt[u]-1) << endl;*/
reroot(v, u);
remnode(v, u, w);
addnode(u, v, w);
}
}
void solve() {
cin >> n >> k;
gp = VVPI(n);
rep(i, n-1) {
int u, v, w;
cin >> u >> v >> w;
gp[u].pb({v, w});
gp[v].pb({u, w});
}
ans = TLE::solve(gp, k);
for (ll x : ans) cout << x << " "; cout << endl;
ans = VL(n);
dp = VVL(n, VL(k+1));
/* dp[u][x]
* how many roads visit city u with fuel x (from subtree of u)
*/
ans = VL(n);
sbt = VI(n);
dfs();
/*rep(u, n) cout << u << ": " << sbt[u] << endl;*/
reroot();
for (ll x : ans) cout << x << " "; cout << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
/*freopen("mincross.in", "r", stdin); */
/*freopen("test.out", "w", stdout); */
int t = 1;
/*cin >> t; */
while (t--) solve();
}
Compilation message
Main.cpp: In function 'void TLE::dfs(int, int, int)':
Main.cpp:44:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
44 | for (auto[v, w] : gp[u]) if (v != p) {
| ^
Main.cpp: In function 'void dfs(int, int)':
Main.cpp:93:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
93 | for (auto[v, w] : gp[u]) if (v != p) {
| ^
Main.cpp: In function 'void reroot(int, int)':
Main.cpp:105:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
105 | for (auto[v, w] : gp[u]) if (v != p) {
| ^
Main.cpp: In function 'void solve()':
Main.cpp:132:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
132 | for (ll x : ans) cout << x << " "; cout << endl;
| ^~~
Main.cpp:132:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
132 | for (ll x : ans) cout << x << " "; cout << endl;
| ^~~~
Main.cpp:144:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
144 | for (ll x : ans) cout << x << " "; cout << endl;
| ^~~
Main.cpp:144:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
144 | for (ll x : ans) cout << x << " "; cout << endl;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
