Petrol Stations

ThegeekKnight16

Jul 13th, 2024

101

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 4.64 KB | None | 0 0

raw download clone embed print report

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 7e4 + 10;
const int border = (int)1e15;
array<vector<pair<int, int>>, MAXN> grafo;
array<int, MAXN> sub, prof, removed, fuel, fuelPai;
vector<int> resp;
struct SparseSeg
{
protected:
vector<int> seg, e, d;
public:
SparseSeg() {seg.reserve((int)MAXN*log2(border)); e.reserve((int)MAXN*log2(border)); d.reserve((int)MAXN*log2(border));}
int create()
{
seg.push_back(0);
e.push_back(0);
d.push_back(0);
return seg.size()-1;
}
int getLeft(int pos)
{
if (e[pos] == 0) {int aux = create(); e[pos] = aux;}
return e[pos];
}
int getRight(int pos)
{
if (d[pos] == 0) {int aux = create(); d[pos] = aux;}
return d[pos];
}
void init()
{
seg.clear(); e.clear(); d.clear();
create(); create();
}
void update(int pos, int ini, int fim, int id, int val)
{
if (id < ini || id > fim) return;
if (ini == fim)
{
seg[pos] += val;
return;
}
int m = (ini + fim) >> 1;
if (id <= m) update(getLeft(pos), ini, m, id, val);
else update(getRight(pos), m+1, fim, id, val);
seg[pos] = seg[e[pos]] + seg[d[pos]];
}
int query(int pos, int ini, int fim, int p, int q)
{
if (q < ini || p > fim || pos == 0 || q < p) return 0;
if (p <= ini && fim <= q) return seg[pos];
int m = (ini + fim) >> 1;
return (query(e[pos], ini, m, p, q) + query(d[pos], m+1, fim, p, q));
}
} carGoes;
void dfsInit(int v, int p)
{
sub[v] = 1;
for (auto [viz, pes] : grafo[v])
{
if (viz == p) continue;
if (removed[viz]) continue;
dfsInit(viz, v);
sub[v] += sub[viz];
}
}
int findCentroid(int v, int p, int N)
{
for (auto [viz, pes] : grafo[v])
{
if (viz == p) continue;
if (removed[viz]) continue;
if (sub[viz] > N/2) return findCentroid(viz, v, N);
}
return v;
}
void dfsVem(int v, int p, int e, vector<int> &path, int K, int mult, vector<int> &close)
{
prof[v] = prof[p] + e; fuel[v] = 1; if (prof[v] <= K) close.push_back(v);
path.push_back(v);
for (auto [viz, pes] : grafo[v])
{
if (viz == p || removed[viz]) continue;
dfsVem(viz, v, pes, path, K, mult, close);
}
path.pop_back(); resp[v] += ((fuel[v]-1) * mult);
if (prof[v] - prof[path[0]] > K)
{
int ini = 0, fim = path.size()-1;
while (ini < fim)
{
int m = (ini + fim) >> 1;
int x = path[m];
if (prof[v] - prof[x] <= K) fim = m;
else ini = m+1;
}
fuel[path[fim]] += fuel[v];
}
}
void dfsSai(int v, int p, int K)
{
fuelPai[v] = 0;
fuelPai[v] = carGoes.query(1, -border, border, prof[p]-K, prof[v]-K-1);
resp[p] += fuelPai[v] * sub[v];
carGoes.update(1, -border, border, prof[p], fuelPai[v]);
for (auto [viz, pes] : grafo[v])
{
if (viz == p || removed[viz]) continue;
dfsSai(viz, v, K);
}
carGoes.update(1, -border, border, prof[p], -fuelPai[v]);
}
void decompose(int v, int N, int K)
{
carGoes.init();
dfsInit(v, N+1);
int c = findCentroid(v, v, sub[v]);
dfsInit(c, N+1); prof[c] = 0;
vector<vector<int>> close;
for (auto [viz, pes] : grafo[c])
{
close.emplace_back();
if (removed[viz]) continue;
vector<int> path(1, c);
dfsVem(viz, c, pes, path, K, sub[c] - sub[viz], close.back());
for (auto x : close.back()) carGoes.update(1, -border, border, -prof[x], fuel[x]);
}
carGoes.update(1, -border, border, 0, 1);
for (int i = 0; i < grafo[c].size(); i++)
{
auto [viz, pes] = grafo[c][i];
if (removed[viz]) continue;
for (auto x : close[i]) carGoes.update(1, -border, border, -prof[x], -fuel[x]);
dfsSai(viz, c, K);
for (auto x : close[i]) carGoes.update(1, -border, border, -prof[x], fuel[x]);
}
close.clear();
removed[c] = 1;
for (auto [viz, pes] : grafo[c]) if (!removed[viz]) decompose(viz, N, K);
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, K;
cin >> N >> K;
resp.resize(N);
for (int i = 1; i < N; i++)
{
int X, Y, P;
cin >> X >> Y >> P;
grafo[X].emplace_back(Y, P);
grafo[Y].emplace_back(X, P);
}
decompose(0, N, K);
for (auto x : resp) cout << x << '\n';
}

Add Comment

Please, Sign In to add comment