题解：P11241 「KTSC 2024 R2」病毒

· · 题解

考虑一个建图方式：建立 n 个点表示病毒的中转点，对每个人的点 i，找到所有距离 p_i 小于等于 d_i 的树上点，它们的中转点向 i 连 0 的边，i 向它们的中转点连 c_i 的边。直接跑 dij 可以做到 O(n^2\log n)。

考虑优化“i 这个人向所有距离它小于等于 d_i 的中转点连权值为 v 的正向或反向边”。考虑点分治优化，一个深度为 dep_i 的点能向所有深度小于等于 d_i-dep_i 的点连边。下面以正向为例：考虑建立 dep+1 个虚点，每个虚点向该深度下的实际中转点连 v 的边；虚点之间由深度 x\to x-1 连 0 边；考察每个人对应的点，向 d_i-dep_i 对应的虚点连 0 边。反向边只需要将上述所有边反向，且去掉虚点连出来的边的权值即可。

这样，点分治过程中每个连通块的点、边数为 O(size)，总数为 O(n\log n) 级别。直接跑 dij 可以做到 O(n\log^2 n)，已经可以通过了。

还有一些优化。对于每个中转点，我们再拆成入点和出点，这样只有 O(n) 条出入点之间的边有权值。在 dij 的过程中，我们借用 01BFS 的思想，对于有权值的边，我们扔进优先队列；对于 0 权边，我们使用普通队列，直接维护。每次弹出时，优先弹出普通堆的点即可。这样只有 O(n) 条边会进堆，复杂度做到 O(n\log n)。似乎优化效果不明显。

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define repp(i,j,k) for(int i=j;i>=k;i--)
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define lowbit(i) (i&-i)
#define qingbai qwq
using namespace std;
typedef long long ll;
const int N=1e5+5,M=2e6+5,mo=1e9+7;
const ll inf=(ll)1e18+7;
void read(int &a){
    int x=0,w=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    a=x*w;
}
int n,m,p[N],d[N],c[N];
vector<int>et[N];
int cntp,id[N];
vector<int>perc[N];
int maxs[N],sz[N],rt,tot;
bool vis[N];
void dfs1(int x,int f){
    maxs[x]=0,sz[x]=1;
    for(auto j:et[x]){
        if(vis[j]||j==f)continue;
        dfs1(j,x),sz[x]+=sz[j],maxs[x]=max(maxs[x],sz[j]);
    }
    maxs[x]=max(maxs[x],tot-sz[x]);
    if(maxs[x]<maxs[rt])rt=x;
}
vector<pii>e[N*45];
int dep[N],idd[N],maxd=0;
void dfs2(int x,int f){
    dep[x]=dep[f]+1,maxd=max(maxd,dep[x]);
    for(auto j:et[x]){
        if(j==f||vis[j])continue;
        dfs2(j,x);
    }
}
void dfs3(int x,int f){
    for(auto j:et[x])
        if(j!=f&&!vis[j])dfs3(j,x);
    for(auto j:perc[x]){
        int topos=min(maxd,d[j]-dep[x]);
        if(topos<0)continue;
        e[id[j]].push_back(mp(idd[topos],0));
        e[idd[topos]+1].push_back(mp(id[j],0));
    }
    e[idd[dep[x]]].push_back(mp(x,0));
    e[x+n].push_back(mp(idd[dep[x]]+1,0));
}
void dfz(int x){
    maxd=0,dep[0]=-1,dfs2(x,0);
    rep(i,0,maxd)
        idd[i]=++cntp,cntp++;
    rep(i,1,maxd){
        e[idd[i]].push_back(mp(idd[i-1],0));
        e[idd[i-1]+1].push_back(mp(idd[i]+1,0));
    }
    dfs3(x,0);
    vis[x]=1;
    for(auto j:et[x]){
        if(vis[j])continue;
        rt=0,tot=sz[j],dfs1(j,x),dfz(rt);
    }
}
ll dis[N*45];
bool visd[N*45];
void dij(){
    queue<pair<ll,int>>q;
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>pq;
    rep(i,1,cntp)
        dis[i]=inf,visd[i]=0;
    dis[id[1]]=0,pq.push(mp(0ll,id[1]));
    while(!q.empty()||!pq.empty()){
        int x;ll v;
        if(!q.empty())tie(v,x)=q.front(),q.pop();
        else tie(v,x)=pq.top(),pq.pop();
        if(visd[x])continue;
        visd[x]=1;
        for(auto j:e[x]){
            if(visd[j.fir]||dis[j.fir]<=dis[x]+j.sec)continue;
            dis[j.fir]=dis[x]+j.sec;
            if(!j.sec)q.push(mp(dis[j.fir],j.fir));
            else pq.push(mp(dis[j.fir],j.fir));
        }
    }
}
vector<ll>ans;
vector<long long> find_spread(int N, int M, vector<int> A, vector<int> B, vector<int> P, vector<int> D, vector<int> C){
    n=N,m=M,cntp=2*n;
    rep(i,0,n-2)
        et[A[i]+1].push_back(B[i]+1),et[B[i]+1].push_back(A[i]+1);
    rep(i,1,m)
        p[i]=P[i-1]+1,d[i]=D[i-1],perc[p[i]].push_back(i);
    rep(i,1,n)
        c[i]=C[i-1];
    rep(i,1,m)
        id[i]=++cntp;
    tot=n,rt=0,maxs[0]=n+2,dfs1(1,0),dfz(rt);
    rep(i,1,n)
        e[i].push_back(mp(i+n,c[i]));
    dij();
    rep(i,1,m){
        if(dis[id[i]]==inf)ans.push_back(-1);
        else ans.push_back(dis[id[i]]);
    }
    return ans;
}