题解：P10805 [CEOI 2024] 加油站

· · 题解

对于链，可以求出以每个点为起点往后走第一个加油的位置，不难以此 dp。

考虑点分治，对应的还要编出一个倒过来的做法：求出其面第一个加油位置在某点的区间，也可以类似 dp。

然后放到树上，只考虑跨过重心的路径。上面两个东西都不难用倍增求解，然后把路径分成三段（第一个子树内，跨过重心，第二个子树）。

对于第一段和第三段直接在每个子树内部传一下即可。第二段需要考虑子树对其他子树的贡献，经典容斥成全集贡献减去自己的贡献，容易用离散化前缀和维护。

复杂度显然就是 O(n\log^2n)，一点都不卡常。然后为了方便你状态最好不要设到根上，这样可以有效减少对根的特判。

:::success[点击查看参考代码]

#include<bits/stdc++.h>
#define TIME chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count()
#define rep(i,l,r) for(int qwp=(r),i=(l);i<=qwp;i++)
#define per(i,r,l) for(int qwp=(l),i=(r);i>=qwp;i--)
#define pb push_back
#define clr clear
#define LB lower_bound
#define UB upper_bound
using namespace std;
namespace ax_by_c{
typedef long long ll;
constexpr ll llinf=3e16;
constexpr int intinf=1e9;
constexpr int N=7e4+5;
constexpr int LN=17;
inline ll frll(){ll n=0;char c=getchar();while(c<'0'||'9'<c)c=getchar();while('0'<=c&&c<='9')n=n*10+c-48,c=getchar();return n;}
void wrll(ll x){if(x>9)wrll(x/10);putchar(x%10+48);}
int n;ll k,ans[N];struct Edge{int v;ll w;};vector<Edge>g[N];
int asz,sz[N],fa[N],rt,rtv;ll de[N];bool del[N];vector<int>nd;
void dfs1(int u){
    nd.pb(u),sz[u]=1;int val=0;
    for(auto e:g[u])if(!del[e.v]&&e.v!=fa[u])fa[e.v]=u,de[e.v]=de[u]+e.w,dfs1(e.v),sz[u]+=sz[e.v],val=max(val,sz[e.v]);
    val=max(val,asz-sz[u]);if(val<rtv)rtv=val,rt=u;
}
int lt[N][LN],up[N];ll f[N],ff[N];
void dfs2(int u,int os){f[u]=1;for(auto e:g[u])if(fa[e.v]==u)dfs2(e.v,os);if(up[u]!=-1)f[up[u]]+=f[u],ans[up[u]]+=f[u]*os,f[u]=0;}
vector<int>snd;
void dfs3(int u){snd.pb(u);for(auto e:g[u])if(fa[e.v]==u)dfs3(e.v);}
ll hsh[N],sum[N];int hc;
void work(vector<int> &a,int z){
    hc=0;for(auto u:a)if(de[u]<=k&&u!=rt)hsh[++hc]=de[u];
    sort(hsh+1,hsh+1+hc),hc=unique(hsh+1,hsh+1+hc)-hsh-1;
    rep(i,1,hc)sum[i]=0;for(auto u:a)if(de[u]<=k&&u!=rt)sum[LB(hsh+1,hsh+1+hc,de[u])-hsh]+=f[u]*z;
    rep(i,1,hc)sum[i]+=sum[i-1];
    for(auto u:a)if(u!=rt)ff[u]+=sum[UB(hsh+1,hsh+1+hc,k-de[fa[u]])-hsh-1]-sum[UB(hsh+1,hsh+1+hc,k-de[u])-hsh-1];
}
ll ffs[N];
void dfs4(int u,ll w){
    ffs[u]=ffs[fa[u]];
    if(de[u]>k){
        int p=u;per(j,LN-1,0)if(de[fa[lt[p][j]]]>=de[u]-k)p=lt[p][j];
        ff[u]+=ffs[fa[p]];
        p=u;per(j,LN-1,0)if(de[fa[lt[p][j]]]>=de[fa[u]]-k)p=lt[p][j];
        ff[u]-=ffs[fa[p]];
    }
    ffs[u]=ffs[fa[u]]+ff[u],ans[fa[u]]+=ff[u]*sz[u];
    for(auto e:g[u])if(!del[e.v]&&fa[e.v]==u){ll x=w;if(x<e.w)x=k,ans[u]+=sz[e.v];x-=e.w;dfs4(e.v,x);}
}
void dfz(int pp,int asz_){
    asz=asz_,rtv=intinf,fa[pp]=0,dfs1(pp);
    fa[rt]=0,de[rt]=0,nd.clr(),dfs1(rt);
    for(auto u:nd)lt[u][0]=fa[u];rep(j,1,LN-1)for(auto u:nd)lt[u][j]=lt[lt[u][j-1]][j-1];
    for(auto u:nd)if(u!=rt&&de[u]>k){up[u]=u;per(j,LN-1,0)if(de[u]-de[lt[up[u]][j]]<=k)up[u]=lt[up[u]][j];}else up[u]=-1;
    for(auto e:g[rt])if(!del[e.v])dfs2(e.v,asz-sz[e.v]);
    for(auto u:nd)ff[u]=0;
    work(nd,1);for(auto e:g[rt])if(!del[e.v])snd.clr(),dfs3(e.v),work(snd,-1);
    dfs4(rt,k);
    del[rt]=1;pp=rt;for(auto e:g[pp])if(!del[e.v])dfz(e.v,sz[e.v]);
}
void main(){
    n=frll(),k=frll();
    rep(i,1,n-1){int x,y;ll w;x=frll()+1,y=frll()+1,w=frll(),g[x].pb({y,w}),g[y].pb({x,w});}
    dfz(1,n);rep(i,1,n)wrll(ans[i]),putchar('\n');
}
}
int main(){
    auto _Tst=TIME;
    // freopen("stations.in","r",stdin);
    // freopen("stations.out","w",stdout);
    ax_by_c::main();
    auto _Ted=TIME;
    cerr<<"\nTIME:"<<_Ted-_Tst<<'\n';
    return 0;
}
/*
ulimit -s 1048576
g++ -O2 -std=c++14 -static stations.cpp -o stations.exe
g++ -O2 -std=c++14 -fsanitize=address,leak,undefined stations.cpp -o stations.exe
./stations.exe
*/

:::