#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 70004;
int n;
ll k;
vector<pair<int, ll> > g[N];
bool c[N];
int q[N];
void dfs0(int x, int p)
{
q[x] = 1;
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i].fi;
if (h == p)
continue;
if (c[h])
continue;
dfs0(h, x);
q[x] += q[h];
}
}
int dfsc(int x, int p, int xx)
{
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i].fi;
if (h == p)
continue;
if (c[h])
continue;
if (q[h] > q[xx] / 2)
return dfsc(h, x, xx);
}
return x;
}
ll ans[N];
const int m = 17;
int pp[N][m];
ll ss[N][m];
int tin[N], tout[N], ti;
void dfs1(int x, int p, ll dp)
{
tin[x] = ++ti;
pp[x][0] = p;
ss[x][0] = dp;
for (int i = 1; i < m; ++i)
{
pp[x][i] = pp[pp[x][i - 1]][i - 1];
ss[x][i] = ss[x][i - 1] + ss[pp[x][i - 1]][i - 1];
}
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i].fi;
ll d = g[x][i].se;
if (h == p)
continue;
if (c[h])
continue;
dfs1(h, x, d);
}
tout[x] = ti;
}
bool isp(int x, int y)
{
return (tin[x] <= tin[y] && tin[y] <= tout[x]);
}
int FU(int x, ll k)
{
ll s = 0;
for (int i = m - 1; i >= 0; --i)
{
if (s + ss[x][i] <= k)
{
s += ss[x][i];
x = pp[x][i];
}
}
return x;
}
void dfst(int x, int p, vector<int>& v)
{
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i].fi;
if (h == p)
continue;
if (c[h])
continue;
dfst(h, x, v);
}
v.push_back(x);
}
int hav[N];
void ubd(vector<int>& t, int tl, int tr, int x, int y, int pos)
{
if (tl == tr)
{
t[pos] += y;
return;
}
int m = (tl + tr) / 2;
if (x <= m)
ubd(t, tl, m, x, y, pos * 2);
else
ubd(t, m + 1, tr, x, y, pos * 2 + 1);
t[pos] = t[pos * 2] + t[pos * 2 + 1];
}
int qry(vector<int>& t, int tl, int tr, int l, int r, int pos)
{
if (l > r)
return 0;
if (tl == l && tr == r)
return t[pos];
int m = (tl + tr) / 2;
return (qry(t, tl, m, l, min(m, r), pos * 2) +
qry(t, m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}
void solvv(int r)
{
dfs0(r, r);
dfs1(r, r, 0);
map<int, vector<pair<ll, int> > > mp;
for (int i = 0; i < g[r].size(); ++i)
{
int x = g[r][i].fi;
int cx = x;
if (c[x])
continue;
vector<int> v;
dfst(x, r, v);
for (int i = 0; i < sz(v); ++i)
hav[v[i]] = 1;
for (int i = 0; i < sz(v); ++i)
{
int x = v[i];
int y = FU(x, k);
if (y == r)
{
mp[cx].push_back(m_p(ss[x][m - 1], hav[x]));
}
else
{
ans[y] += hav[x] * 1LL * (q[r] - sz(v));
hav[y] += hav[x];
}
}
}
vector<ll> xt;
for (auto it = mp.begin(); it != mp.end(); ++it)
{
for (int i = 0; i < sz(it->se); ++i)
{
xt.push_back(it->se[i].fi);
}
}
sort(all(xt));
vector<int> t(sz(xt) * 4 + 10, 0);
for (auto it = mp.begin(); it != mp.end(); ++it)
{
for (int i = 0; i < sz(it->se); ++i)
{
ubd(t, 1, sz(xt), lower_bound(all(xt), it->se[i].fi) - xt.begin() + 1, it->se[i].se, 1);
}
}
int root = r;
for (int i = 0; i < g[r].size(); ++i)
{
int x = g[r][i].fi;
if (c[x])
continue;
vector<int> v;
dfst(x, r, v);
reverse(all(v));
for (int i = 0; i < sz(mp[x]); ++i)
{
ubd(t, 1, sz(xt), lower_bound(all(xt), mp[x][i].fi) - xt.begin() + 1, -mp[x][i].se, 1);
}
for (int i = 0; i < sz(v); ++i)
hav[v[i]] = 0;
hav[r] = 0;
for (int i = 0; i < sz(v); ++i)
{
int x = v[i];
ll r = k - ss[pp[x][0]][m - 1];
ll l = k - ss[x][m - 1] + 1;
if (l <= r)
{
int l2 = lower_bound(all(xt), l) - xt.begin() + 1;
int r2 = upper_bound(all(xt), r) - xt.begin();
if (l2 <= r2)
{
assert(1 <= l2 && r2 <= sz(xt));
ans[pp[x][0]] += qry(t, 1, sz(xt), l2, r2, 1) * 1LL * q[x];
hav[pp[x][0]] += qry(t, 1, sz(xt), l2, r2, 1);
}
}
if (ss[x][m - 1] > k && ss[pp[x][0]][m - 1] <= k)
{
ans[pp[x][0]] += q[x];
hav[pp[x][0]] += 1;
}
if (ss[x][m - 1] > k)
{
int y = FU(pp[x][0], k);
int z = pp[FU(x, k)][0];
int yy = 0;
int zz = 0;
if (ss[pp[x][0]][m - 1] > k)
{
yy = FU(pp[pp[x][0]][0], k);
zz = pp[FU(pp[x][0], k)][0];
}
int xx = x;
while (1)
{
if (yy)
{
if (isp(yy, xx) && isp(xx, zz))
{
assert(!(isp(y, xx) && isp(xx, z)));
continue;
}
}
if (isp(y, xx) && isp(xx, z))
{
ans[pp[x][0]] += hav[xx] * 1LL * q[x];
hav[pp[x][0]] += hav[xx];
}
if (xx == root)
break;
xx = pp[xx][0];
}
}
}
for (int i = 0; i < sz(mp[x]); ++i)
{
ubd(t, 1, sz(xt), lower_bound(all(xt), mp[x][i].fi) - xt.begin() + 1, mp[x][i].se, 1);
}
}
}
vector<ll> solv()
{
for (int i = 0; i <= n + 1; ++i)
{
c[i] = false;
ans[i] = 0;
}
queue<int> q;
q.push(1);
while (!q.empty())
{
int x = q.front();
q.pop();
dfs0(x, x);
x = dfsc(x, x, x);
solvv(x);
c[x] = true;
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i].fi;
if (!c[h])
q.push(h);
}
}
vector<ll> ansv;
for (int x = 1; x <= n; ++x)
ansv.push_back(ans[x]);
for (int x = 1; x <= n; ++x)
cout << ans[x] << "\n";
return ansv;
}
bool dfsg(int x, int p, int y, vector<ll>& v, vector<int>& u)
{
if (x == y)
return true;
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i].fi;
if (h == p)
continue;
v.push_back(g[x][i].se);
u.push_back(x);
if (dfsg(h, x, y, v, u))
return true;
u.pop_back();
v.pop_back();
}
return false;
}
vector<ll> solv0()
{
for (int i = 0; i <= n + 1; ++i)
ans[i] = 0;
for (int x = 1; x <= n; ++x)
{
for (int y = 1; y <= n; ++y)
{
vector<ll> v;
vector<int> u;
assert(dfsg(x, x, y, v, u));
ll s = 0;
for (int i = 0; i < sz(v); ++i)
{
if (s + v[i] > k)
{
s = 0;
++ans[u[i]];
}
s += v[i];
}
}
}
vector<ll> ansv;
for (int x = 1; x <= n; ++x)
ansv.push_back(ans[x]);
return ansv;
}
int main()
{
#ifdef SOMETHING
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif // SOMETHING
ios_base::sync_with_stdio(false), cin.tie(0);
int st = 1000;
while (st--)
{
n = rnf() % 5 + 2;
k = rnf() % 1 + 1;
for (int x = 1; x <= n; ++x)
g[x].clear();
vector<pair<pair<int, int>, int> > b;
for (int x = 2; x <= n; ++x)
{
int y = rnf() % (x - 1) + 1;
int z = rnf() % (k + 1);
g[x].push_back(m_p(y, z));
g[y].push_back(m_p(x, z));
b.push_back(m_p(m_p(x, y), z));
}
auto myans = solv();
auto trueans = solv0();
if (myans != trueans)
{
solv();
solv0();
cout << "WA\n";
cout << n << ' ' << k << "\n";
for (int i = 0; i < n - 1; ++i)
cout << b[i].fi.fi << ' ' << b[i].fi.se << ' ' << b[i].se << "\n";
cout << "MY\n";
for (int i = 0; i < sz(myans); ++i)
cout << myans[i] << "\n";
cout << "TRUE\n";
for (int i = 0; i < sz(trueans); ++i)
cout << trueans[i] << "\n";
cout << endl;
return 0;
}
}
cout << "OK" << endl;
return 0;
int tt = 1;
//cin >> tt;
while (tt--)
{
cin >> n >> k;
for (int i = 0; i < n - 1; ++i)
{
int x, y, z;
cin >> x >> y >> z;
++x;
++y;
g[x].push_back(m_p(y, z));
g[y].push_back(m_p(x, z));
}
solv();
}
return 0;
}
Compilation message
Main.cpp: In function 'void dfs0(int, int)':
Main.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for (int i = 0; i < g[x].size(); ++i)
| ~~^~~~~~~~~~~~~
Main.cpp: In function 'int dfsc(int, int, int)':
Main.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for (int i = 0; i < g[x].size(); ++i)
| ~~^~~~~~~~~~~~~
Main.cpp: In function 'void dfs1(int, int, ll)':
Main.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for (int i = 0; i < g[x].size(); ++i)
| ~~^~~~~~~~~~~~~
Main.cpp: In function 'void dfst(int, int, std::vector<int>&)':
Main.cpp:99:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for (int i = 0; i < g[x].size(); ++i)
| ~~^~~~~~~~~~~~~
Main.cpp: In function 'void solvv(int)':
Main.cpp:144:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | for (int i = 0; i < g[r].size(); ++i)
| ~~^~~~~~~~~~~~~
Main.cpp:190:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
190 | for (int i = 0; i < g[r].size(); ++i)
| ~~^~~~~~~~~~~~~
Main.cpp: In function 'std::vector<long long int> solv()':
Main.cpp:286:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
286 | for (int i = 0; i < g[x].size(); ++i)
| ~~^~~~~~~~~~~~~
Main.cpp: In function 'bool dfsg(int, int, int, std::vector<long long int>&, std::vector<int>&)':
Main.cpp:306:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
306 | for (int i = 0; i < g[x].size(); ++i)
| ~~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3536 ms |
5208 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3536 ms |
5208 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3542 ms |
5212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3536 ms |
5208 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3536 ms |
5208 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3536 ms |
5208 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3536 ms |
5208 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
