#include <bits/stdc++.h>
#define int long long
//#warning("nu uita de clear la aint")
using namespace std;
using i64=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;
namespace aint
{
const i64 MAX_VAL=1LL*inf*N;
struct node
{
i64 sum;
node*l,*r;
node()
{
sum=0;
l=r=nullptr;
}
};
node* root=nullptr;
void clear(node*& t)
{
if(t==nullptr)
{
return;
}
clear(t->l);
clear(t->r);
delete t;
t=nullptr;
}
void clear()
{
clear(root);
}
i64 get_val(node* t)
{
if(t==nullptr)
{
return 0;
}
return t->sum;
}
void update(node*& t,i64 st,i64 dr,i64 poz,i64 val)
{
if(t==nullptr)t=new node;
t->sum+=val;
if(st==dr)
{
return;
}
i64 m=(st+dr)/2;
if(poz<=m)
{
update(t->l,st,m,poz,val);
}
else
{
update(t->r,m+1,dr,poz,val);
}
}
i64 query(node*& t,i64 st,i64 dr,i64 l,i64 r)
{
if(t==nullptr || st>r || dr<l)
{
return 0;
}
if(l<=st && dr<=r)
{
return t->sum;
}
i64 m=(st+dr)/2;
return query(t->l,st,m,l,r)+query(t->r,m+1,dr,l,r);
}
void update(i64 poz,i64 k)
{
update(root,0,MAX_VAL,poz,k);
}
i64 query(i64 l,i64 r)
{
return query(root,0,MAX_VAL,l,r);
}
}
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;
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)
{
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
carry[lower_bound(all(sk) , (pair<int,int>){h[nod]-k,0})->second]+=carry[nod];
}
else
{
mp[comp[nod]].push_back({k-h[nod],carry[nod]});
}
sk.pop_back();
}
void insert(int nod,int tt,int sign)
{
if(h[nod]>k)
{
return;
}
aint::update(k-h[nod],sign*carry[nod]);
for(auto &v:adj[nod])
{
int c=v.to;
if(c!=tt && !viz[c])
{
insert(c,nod,sign);
}
}
}
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::update(v.first,-v.second);
}
}
i64 coef=aint::query(h[nod],h[c]-1);
sol[nod]+=coef*subtree[c];
aint::update(h[nod]+k,coef);
solve(c,nod,total);
aint::update(h[nod]+k,-coef);
if(h[nod]==0)
{
for(auto &v:mp[comp[c]])
{
aint::update(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);
for(auto &v:mp)
{
for(auto &c:v.second)
{
aint::update(c.first,c.second);
}
}
solve(nod,nod,subtree[nod]);
aint::clear();
mp.clear();
viz[nod]=true;
for(auto &c:adj[nod])
{
if(!viz[c.to])
{
decomp(c.to);
}
}
}
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';
}
}
Compilation message
Main.cpp:240:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
240 | main()
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
4864 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 |
671 ms |
15572 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 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 |
671 ms |
15572 KB |
Output is correct |
| 5 |
Correct |
2229 ms |
72928 KB |
Output is correct |
| 6 |
Correct |
2695 ms |
65564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 3 |
Incorrect |
632 ms |
8832 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 |
1 ms |
4688 KB |
Output is correct |
| 3 |
Incorrect |
632 ms |
8832 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 |
1 ms |
4688 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
4864 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
