题解：P10805 [CEOI 2024] 加油站

· · 题解

无脑硬维护做法！

起手套一个点分治，然后考虑每个点分成两种贡献：

考虑第一个咋做，发现要维护的操作相当于：

这些东西直接上平衡树用脚维护，不过要注意平衡树有交合并需要把值相同的点缩起来，不然复杂度会寄。

考虑第二个咋做，你发现不能直接套平衡树了，因为如果硬套还需要可持久化，上面这些操作肯定不支持，那么考虑一些其他能可持久化的结构，容易想到主席树。

因为你是从根一直到某个点，所以就不会有合并操作，值域线段树上容易维护前两种操作，因为是单点修改所以可以可持久化，第三种操作因为是全局的，所以直接将整体下标偏移一下即可，那么这个题就做完了！

时间复杂度 O(n\log^2n\log v)，常数不大跑的飞快。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=70010,inf=1e14;
int n,k;
vector<pair<int,int> >g[N];
struct node{
    int l,r,x,cnt,s,add;
    unsigned int rk;
};
int frt[N],tot1,tot2,drt[N];
int sz[N],vis[N],ans[N];
struct qwq{
    int l,r,x;
};
struct SEG{
    qwq tr[N<<7];
    void update(int l,int r,int &p1,int p2,int x,int v){
        if(!p1){
            p1=++tot2;
            tr[p1]={0,0,0};
        }
        if(l==r){
            tr[p1].x=tr[p2].x+v;
            return;
        }
        int mid=(l+r)>>1;
        if(x<=mid){
            tr[p1].r=tr[p2].r;
            update(l,mid,tr[p1].l,tr[p2].l,x,v);
        }else{
            tr[p1].l=tr[p2].l;
            update(mid+1,r,tr[p1].r,tr[p2].r,x,v); 
        } 
        tr[p1].x=tr[tr[p1].l].x+tr[tr[p1].r].x;
    }
    int query(int l,int r,int p,int a,int b){
        if(!p)return 0;
        if(l>b||r<a)return 0;
        if(a<=l&&r<=b)return tr[p].x;
        int mid=(l+r)>>1;
        return query(l,mid,tr[p].l,a,b)+query(mid+1,r,tr[p].r,a,b);
    }
}P; 
struct FHQ{
    node tr[N<<4];
    void updadd(int p,int v){
        tr[p].x+=v;
        tr[p].add+=v;
    }
    void pushdown(int p){
        if(tr[p].add){
            updadd(tr[p].l,tr[p].add);
            updadd(tr[p].r,tr[p].add);
            tr[p].add=0;
        }       
    }
    void pushup(int p){
        tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+tr[p].cnt;
        if(tr[p].x==tr[tr[p].l].x)
            tr[p].cnt+=tr[tr[p].l].cnt,tr[p].l=merge(tr[tr[p].l].l,tr[tr[p].l].r);
        else if(tr[p].x==tr[tr[p].r].x)
            tr[p].cnt+=tr[tr[p].r].cnt,tr[p].r=merge(tr[tr[p].r].l,tr[tr[p].r].r);
    }
    void spilt(int v,int p,int &x,int &y){
        if(!p){
            x=y=0;
            return;
        }
        pushdown(p);
        if(tr[p].x<=v){
            x=p;
            spilt(v,tr[p].r,tr[p].r,y);
        }else{
            y=p;
            spilt(v,tr[p].l,x,tr[p].l);
        }
        pushup(p);
    }
    int merge(int x,int y){
        if(!x||!y)return x|y;
        pushdown(x);pushdown(y);
        if(tr[x].rk<tr[y].rk){
            int L=0,R=0;
            spilt(tr[x].x,y,L,R);
            tr[x].l=merge(tr[x].l,L);
            tr[x].r=merge(tr[x].r,R);
            pushup(x);
            return x;
        }else{
            int L=0,R=0;
            spilt(tr[y].x,x,L,R);
            tr[y].l=merge(tr[y].l,L);
            tr[y].r=merge(tr[y].r,R);
            pushup(y);
            return y;
        }
    }
    void insert(int &rt,int x,int kw){
        unsigned int y=1ll*rand()*rand()*rand();
        int L=0,R=0;
        spilt(x,rt,L,R);
        if(tr[L].x!=x){
            tr[++tot1]={0,0,x,kw,kw,0,y};
            L=merge(L,tot1);            
        }else{
            tr[L].cnt+=kw;
            tr[L].s+=kw;
        }
        rt=merge(L,R); 
    }
}T;
int rt,nmx;
void getrt(int u,int f,int tl){
    sz[u]=1;
    int mx=0;
    for(auto v:g[u]){
        if(vis[v.first]||v.first==f)continue;
        getrt(v.first,u,tl);
        sz[u]+=sz[v.first]; 
        mx=max(mx,sz[v.first]);
    }
    mx=max(mx,tl-sz[u]);
    if(mx<nmx){
        rt=u;
        nmx=mx;
    }
}
void clear(int u,int f){
    frt[u]=drt[u]=0;
    for(auto v:g[u]){
        if(vis[v.first]||v.first==f)continue;
        clear(v.first,u);
    }
}
void dfs1(int u,int f,int w,int val){
    T.insert(frt[u],k,1);
    for(auto v:g[u]){
        if(vis[v.first]||v.first==f)continue;
        dfs1(v.first,u,v.second,val);
        frt[u]=T.merge(frt[u],frt[v.first]);
    }
    int L=0,R=0;
    T.spilt(w-1,frt[u],L,R);
    ans[u]+=val*T.tr[L].s;
    frt[u]=R;
    if(T.tr[L].s)
    T.insert(frt[u],k,T.tr[L].s);
    T.updadd(frt[u],-w);
}
void dfs2(int u,int f,int id,int w,int s){
    int cnt=P.query(0,inf,id,s,s+w-1);
    ans[f]+=cnt*sz[u];
    P.update(0,inf,drt[u],id,k+s,cnt); 
    s+=w;
    for(auto v:g[u]){
        if(vis[v.first]||v.first==f)continue;
        dfs2(v.first,u,drt[u],v.second,s);
    }
}
int dwq;
void dfs3(int u){
    if(!u)return;
    T.pushdown(u); 
    P.update(0,inf,dwq,dwq,T.tr[u].x,T.tr[u].cnt);
    dfs3(T.tr[u].l);
    dfs3(T.tr[u].r);
}
void getsz(int u,int f){
    sz[u]=1;
    for(auto v:g[u]){
        if(v.first==f||vis[v.first])continue;
        getsz(v.first,u);
        sz[u]+=sz[v.first];
    }
}
void solve(int u,int tl){
    nmx=1e9;rt=0;tot1=0;tot2=0;
    getrt(u,0,tl);
    getsz(rt,0);
    for(auto v:g[rt]){
        if(vis[v.first])continue;
        dfs1(v.first,rt,v.second,tl-sz[v.first]);
    }
    dwq=0;
    P.update(0,inf,dwq,dwq,k,1);
    for(int i=0;i<g[rt].size();i++){
        pair<int,int>v=g[rt][i];
        if(vis[v.first])continue;
        dfs2(v.first,rt,dwq,v.second,0);
        dfs3(frt[v.first]);
    }
    dwq=0;
    for(int i=g[rt].size()-1;i>=0;i--){
        pair<int,int>v=g[rt][i];
        if(vis[v.first])continue;
        dfs2(v.first,rt,dwq,v.second,0);
        dfs3(frt[v.first]);
    }
    clear(rt,0);
    for(int i=0;i<=tot1;i++)T.tr[i]={0,0,0,0,0,0,0};
    for(int i=0;i<=tot2;i++)P.tr[i]={0,0,0};
    vis[rt]=1;
    for(auto v:g[rt]){
        if(vis[v.first])continue;
        solve(v.first,sz[v.first]);
    }
}
signed main(){
    srand(time(0)); 
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        u++;v++;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    solve(1,n);
    for(int i=1;i<=n;i++)cout<<ans[i]<<'\n';
    return 0;
}