#include <bits/stdc++.h>
#define int long long
//#warning("nu uita de clear la aint")
using namespace std;
using i64=long long;
using ll=long long;
#define UNUSED -1
#define all(x) x.begin(),x.end()
#define pb push_back
const int mod=1e9+7,inf=1e9+1;
const i64 INF=1e18;
mt19937 rng(69);
const int N=70'000;
struct edge
{
int to,cost;
};
int n,k;
vector<pair<int,int>>sk;
i64 sol[N],h[N];
int subtree[N],carry[N],comp[N];
vector<edge>adj[N];
bitset<N>viz;
map<int, vector<pair<int, int>>> mp;
struct tree {
int sum = 0;
tree *left_child = nullptr, *right_child = nullptr;
void extend(ll left, ll right) {
if (!left_child && left + 1 < right) {
left_child = new tree();
right_child = new tree();
}
}
void add(ll kk, ll x, ll left = 0, ll right = (n + 1) * k)
{
sum += x;
if (left + 1 < right) {
if (kk < (left + right) / 2)
{
if (!left_child) left_child = new tree();
left_child->add(kk, x, left, (left + right) / 2);
}
else
{
if (!right_child) right_child = new tree();
right_child->add(kk, x, (left + right) / 2, right);
}
}
}
int get_sum(ll lq, ll rq, ll left = 0, ll right = (n + 1) * k) {
if (lq <= left && right <= rq)
return sum;
if (max(left, lq) >= min(right, rq))
return 0;
ll answer = 0;
if (left_child)
answer += left_child->get_sum(lq, rq, left, (left + right) / 2);
if (right_child)
answer += right_child->get_sum(lq, rq, (left + right) / 2, right);
return answer;
}
};
tree* aint=nullptr;
void recalc_dfs(int nod,int tt)
{
subtree[nod]=1;
for(auto &v:adj[nod])
{
int c=v.to;
if(c!=tt && !viz[c])
{
recalc_dfs(c,nod);
subtree[nod]+=subtree[c];
}
}
}
int get_centroid(int nod,int tt,int goal)
{
for(auto &v:adj[nod])
{
int c=v.to;
if(c!=tt && !viz[c] && subtree[c]>=goal)
{
return get_centroid(c,nod,goal);
}
}
return nod;
}
//sa fac functie recurstiva de insert
void go_up(int nod,int tt)
{
if(h[tt]==0 || nod==tt)
{
comp[nod]=nod;
}
else
{
comp[nod]=comp[tt];
}
sk.push_back({h[nod],nod});
carry[nod]=subtree[nod]=1;
for(auto &v:adj[nod])
{
int c=v.to;
if(c!=tt && !viz[c])
{
h[c]=h[nod]+v.cost;
go_up(c,nod);
subtree[nod]+=subtree[c];
}
}
if(h[nod]>k)
{
//next_stop_up
auto it=lower_bound(all(sk) , make_pair(h[nod]-k,0LL));
assert(it->first>=h[nod]-k);
assert(prev(it)->first<h[nod]-k);
carry[lower_bound(all(sk) , make_pair(h[nod]-k,0LL))->second]+=carry[nod];
}
else
{
mp[comp[nod]].push_back({k-h[nod],carry[nod]});
}
sk.pop_back();
}
void solve(int nod,int tt,int total)
{
//deocamdata nu opreste nimeni in root
if(h[nod]>0)
{
sol[nod]+=1LL*(total-subtree[comp[nod]])*(carry[nod]-1);
}
for(auto &v:adj[nod])
{
int c=v.to;
if(c!=tt && !viz[c])
{
if(h[nod]==0)
{
for(auto &v:mp[comp[c]])
{
aint->add(v.first,-v.second);
}
}
i64 coef=aint->get_sum(h[nod],h[c]);
sol[nod]+=coef*subtree[c];
aint->add(h[nod]+k,coef);
solve(c,nod,total);
aint->add(h[nod]+k,-coef);
if(h[nod]==0)
{
for(auto &v:mp[comp[c]])
{
aint->add(v.first,v.second);
}
}
}
}
}
void decomp(int nod)
{
recalc_dfs(nod,nod);
nod=get_centroid(nod,nod,subtree[nod]/2);
h[nod]=0;
go_up(nod,nod);
aint=new tree;
for(auto &v:mp)
{
for(auto &c:v.second)
{
aint->add(c.first,c.second);
}
}
solve(nod,nod,subtree[nod]);
mp.clear();
viz[nod]=true;
for(auto &c:adj[nod])
{
if(!viz[c.to])
{
decomp(c.to);
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>k;
for(int i=1;i<n;i++)
{
int x,y,z;
cin>>x>>y>>z;
adj[x].pb({y,z});
adj[y].pb({x,z});
}
decomp(0);
for(int i=0;i<n;i++)
{
cout<<sol[i]<<'\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4688 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4688 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
6140 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 2 |
Correct |
415 ms |
85184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4688 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 4 |
Correct |
415 ms |
85184 KB |
Output is correct |
| 5 |
Correct |
2084 ms |
1048412 KB |
Output is correct |
| 6 |
Correct |
2104 ms |
1031984 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4688 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 3 |
Incorrect |
330 ms |
67688 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4688 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 3 |
Incorrect |
330 ms |
67688 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4688 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
6140 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
