题解：P9260 [PA 2022] Miny

· · 题解

为什么可持久化线段树合并能过啊。

树上邻域问题，考虑点分治。建出点分树，然后对于每个点提出子树内的所有点，前缀优化建边后双指针扫一轮（笔者的代码使用了暴力跳父亲加二分），可以 O(n\log n) 建出转移图，然后做图上可达点统计即可，位运算优化转移可以做到 O(\dfrac{n^2\log n}{w})，其中 w=64。也就是每次取出 64 个点进行状压，再拓扑排序。

听起来很简单？那你的代码能通过官方的完整数据吗？虽然纸面运算次数只有 3\times10^9，但是前缀优化建边自带 2 倍常数，这就导致某个地方稍微常数大一点就过不了。包括但不限于：

  1. 点分治写挂了，变成了大常数 \log n。

  2. 内存访问不连续，这在暴力题中是致命的。

  3. 前缀优化建图时建出了所有的虚点，而不是只建出需要的点。这会导致缩点后形成的分量过多，约为 2 倍。

  4. 图上转移时没有应用分量标号是逆拓扑序的性质，每次重新进行拓扑排序。

看起来只有内存访问不连续不好解决，因为其余的问题都指出了解决办法。经典的办法是进行边基排，优化十分显著。但此时笔者的代码最慢点要 10 秒，仍然无法通过。问题出在哪里呢？

我们为什么只取 64 个点啊，我缺这点空间？我取 1024 个点状压，于是访问就比较连续了。

参考实现（并没有因为卡常而面目全非）：

#include<bits/stdc++.h>
#define se second
#define fi first
using namespace std;
using ll=long long;
using ull=unsigned long long;
using pli=pair<ll,int>;
using pii=pair<int,int>;
const int INF=0x3f3f3f3f;
const int N=1e5+3;
void ckmn(int &x,int y){if(y<x)x=y;}
struct Edge{int nxt,to;ll w;}e[N*100];
int head[N*35],dfn[N*35],dep[N],f[20][N],fa[N],sz[N],mx[N];
ll dis[N],R[N];
bitset<N*35>vis;
int tot,n,cnt,rt,sum;
void add(int u,int v,ll w=0){
    e[++tot]={head[u],v,w};
    head[u]=tot;
}
void dfs1(int x,int fa){
    f[0][++cnt]=fa;dep[x]=dep[fa]+1;
    dfn[x]=cnt;
    for(int i=head[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(y==fa)continue;
        dis[y]=dis[x]+e[i].w;
        dfs1(y,x);
    }
}
int ckmx(int x,int y){return dep[x]<dep[y]?x:y;}
int lca(int x,int y){
    if(x==y)return x;
    if((x=dfn[x])>(y=dfn[y]))swap(x,y);
    int k=__lg(y-x);
    return ckmx(f[k][x+1],f[k][y-(1<<k)+1]);
}
ll calc(int x,int y){return dis[x]+dis[y]-2*dis[lca(x,y)];}
void getSz(int x,int f){
    sz[x]=1;mx[x]=0;
    for(int i=head[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(y==f||vis[y])continue;
        mx[x]=max(sz[y],mx[x]);
        getSz(y,x);sz[x]+=sz[y];
    }
}
void getRt(int x,int f){
    mx[x]=max(mx[x],sum-sz[x]);
    if(mx[x]<mx[rt])rt=x;
    for(int i=head[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(y==f||vis[y])continue;
        getRt(y,x);
    }
}
void solve(int x){
    vis[x]=1;
    for(int i=head[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(vis[y])continue;
        getSz(y,x);rt=0;sum=sz[y];
        getRt(y,x);fa[rt]=x;
        solve(rt);
    }
}
vector<pli>tmp[N];
vector<int>id[N];
void build(int x,int s){
    tmp[s].push_back({calc(x,s),x});
    for(int i=head[x];i;i=e[i].nxt){
        int y=e[i].to;
        build(y,s);
    }
}
int st[N*35],bl[N*35],low[N*35];
int top,scc;
void tarjan(int x){
    st[++top]=x;vis[x]=1;
    dfn[x]=low[x]=++cnt;
    for(int i=head[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(!dfn[y])tarjan(y),ckmn(low[x],low[y]);
        else if(vis[y])ckmn(low[x],dfn[y]);
    }
    if(low[x]==dfn[x]&&++scc)
        while(1){
            int y=st[top--];
            bl[y]=scc;vis[y]=0;
            if(x==y)break;
        }
}
const int B=1<<10;
int ans[N],MX[N],LD[N*35],RD[N*35],to[N*100],bk[N*100];
vector<int>E[N*35];
bitset<B>g[N*35];
int main(){
    int u,v,x,y,z;ll w;
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i)cin>>R[i];
    for(int i=1;i<n;++i)cin>>u>>v>>w,add(u,v,w),add(v,u,w);
    dfs1(1,0);
    for(int j=1;1<<j<=n;++j)
        for(int i=1;i+(1<<j)-1<=n;++i)
            f[j][i]=ckmx(f[j-1][i],f[j-1][i+(1<<j-1)]);
    mx[0]=INF;getSz(1,0);sum=sz[1];getRt(1,0);solve(rt);
    fill_n(head+1,n,0);tot=0;
    int p=0;
    for(int i=1;i<=n;++i)
        if(fa[i])add(fa[i],i);
        else p=i;
    for(int i=1;i<=n;++i)build(i,i),sort(tmp[i].begin(),tmp[i].end());
    fill_n(head+1,n,0);tot=0;
    int now=n;fill_n(MX+1,n,-1);
    for(int i=1;i<=n;++i)
        for(int x=i;x;x=fa[x]){
            ll k=R[i]-calc(i,x);
            if(k<0)continue;
            int y=upper_bound(tmp[x].begin(),tmp[x].end(),make_pair(k,INF))-tmp[x].begin()-1;
            MX[x]=max(MX[x],y);
        }
    for(int x=1;x<=n;++x){
        if(tmp[x].empty()||MX[x]==-1)continue;
        int len=tmp[x].size();
        id[x].resize(MX[x]+1);
        add(id[x][0]=++now,x);
        for(int i=1;i<=MX[x];++i){
            add(id[x][i]=now+1,now);
            add(id[x][i]=++now,tmp[x][i].se);
        }
    }
    for(int i=1;i<=n;++i)
        for(int x=i;x;x=fa[x]){
            ll k=R[i]-calc(i,x);
            if(k<0)continue;
            int y=upper_bound(tmp[x].begin(),tmp[x].end(),make_pair(k,INF))-tmp[x].begin()-1;
            add(i,id[x][y]);
        }
    vis.reset();cnt=0;fill_n(dfn+1,n,0);
    for(int i=1;i<=now;++i)if(!dfn[i])tarjan(i);
    for(int x=1;x<=now;++x)
        for(int i=head[x];i;i=e[i].nxt)
            if((u=bl[x])!=(v=bl[e[i].to]))
                E[v].push_back(u);
    tot=0;
    for(int x=1;x<=scc;++x){
        sort(E[x].begin(),E[x].end());
        for(auto y:E[x])to[++tot]=y,bk[tot]=x;
    }
    for(int l=1,r;l<=n;l=r+1){
        r=min(l+B-1,n);memset(&g[1],0,128*scc);
        for(int i=l;i<=r;++i)g[bl[i]][i-l]=1;
        for(int i=1;i<=tot;++i)g[to[i]]|=g[bk[i]];
        for(int i=1;i<=n;++i)ans[i]+=g[bl[i]].count();
    }
    for(int i=1;i<=n;++i)printf("%d ",ans[i]);puts("");
    return 0;
}