题解：P14269 [ROI 2015 Day2] 警报系统

· · 题解

Sol

一个暴力做法是，对于每个点，将其向其可以触发的点连有向边，最后答案就是入度为零的 SCC 数。

考虑优化建图，发现每次连边都是给一个距离前缀连边的形式，因此想到前缀和优化建图，然而图上并不方便直接找到与每个点距离前缀的链。

考虑点分治，每个分治块中所有点按分支中心距离升序排序得到一条虚链，然后对分治块中每个点都二分找到这条虚链上可连接的前缀连边。这样连出来的边数是 O(n\log n) 级别的。同一子树中的距离虽然会算错，但只大不小不会影响正确性，因此直接连即可。

值得注意的是，最后算答案时，一些没有被经过过的虚点应当删去，从所有实点搜一遍即可找出要被删除的节点。

最后，时空限制对于我这种大常熟选手来说还是有点紧了。qwq

Code

由于卡常略显丑陋。

const int N=3e5+5,NN=6e6+5;

int n,nn;
ll r[N];
vec<pil> g[N];
vec<int> G[NN];

bool don[N];

int siz,sz[N];
void gsiz(int x,int fa){
    sz[x]=1;
    for(auto e:g[x]){
        int y=e.fir;
        if(y==fa||don[y])continue;
        gsiz(y,x);
        sz[x]+=sz[y];
    }
}
int rot,mx[N];
void grot(int x,int fa){
    mx[x]=siz-sz[x];
    for(auto e:g[x]){
        int y=e.fir;
        if(y==fa||don[y])continue;
        grot(y,x);
        chmax(mx[x],sz[y]);
    }
    if(mx[x]<mx[rot])rot=x;
}
int fa[N];
vec<int> son;
vec<ll> dep;ll dis[N];
int to[N];
void dfs(int x,int fa){
    son.pub(x);dep.pub(dis[x]);++n,G[n].pub(x),to[x]=n;
    for(auto e:g[x]){
        int y=e.fir;
        if(y==fa||don[y])continue;
        dis[y]=dis[x]+e.sec;
        dfs(y,x);
    }
}
void dfs1(int x,int fa){
    ll d=r[x]-dis[x];
    int k=upper_bound(dep.begin(),dep.end(),d)-dep.begin()-1;
    if(k>=0)G[x].pub(to[son[k]]);
    for(auto e:g[x]){
        int y=e.fir;
        if(y==fa||don[y])continue;
        dfs1(y,x);
    }
}
void calc(int x,int Fa){
    gsiz(x,0),siz=sz[x];
    mx[rot=0]=inf,grot(x,0);
    x=rot,fa[x]=Fa;
    son.clear(),dep.clear();
    dis[x]=0;dfs(x,0);
    sort(son.begin(),son.end(),[&](int a,int b){return dis[a]<dis[b];});
    sort(dep.begin(),dep.end());
    int z=x;ll d;int c=1;
    per(i,son.size()-1,1)G[to[son[i]]].pub(to[son[i-1]]);
    dfs1(x,0);
    don[x]=1;
    for(auto e:g[x]){
        int y=e.fir;
        if(don[y])continue;
        calc(y,x);
    }
}

int scnt,dcnt,top;
vec<int> dg,scc,dfn,low,stk;vec<bool> ins,pd,pd2;
void tarjan(int x){
    dfn[x]=low[x]=++dcnt;
    stk[++top]=x,ins[x]=1;
    for(auto y:G[x]){
        if(!dfn[y])tarjan(y),chmin(low[x],low[y]);
        else if(ins[y])chmin(low[x],dfn[y]);
    }
    if(low[x]>=dfn[x]){
        ++scnt;
        while(1){
            int tp=stk[top--];ins[tp]=0;
            scc[tp]=scnt;
            if(tp==x)break;
        }
    }
}
void dfs(int x){
    pd[x]=1;pd2[scc[x]]=pd2[scc[x]]|pd[x];
    for(auto y:G[x])if(!pd[y])dfs(y);
}

inline void Main(){
    cin>>n;nn=n;
    rep(i,1,n)cin>>r[i];
    rep(i,2,n){
        int a,b,c;cin>>a>>b>>c;
        g[a].pub({b,c}),g[b].pub({a,c});
    }
    calc(1,0);
    scc.resize(n+1),dfn.resize(n+1),low.resize(n+1),stk.resize(n+1),ins.resize(n+1),pd.resize(n+1);
    rep(i,1,n)if(!dfn[i])tarjan(i);
    dg.resize(scnt+1),pd2.resize(scnt+1);
    rep(i,1,nn)dfs(i);
    rep(i,1,n)for(auto j:G[i])if(scc[i]!=scc[j]&&pd[i])++dg[scc[j]];
    int ans=0;
    rep(i,1,scnt)if(!dg[i])ans+=pd2[i];
    put(ans);
}