P3783_天才黑客题解

我不是来刷字符串的吗怎么给我干到这里来了

Trie 树神仙题。

形式化题意可以看其他题解的。

首先这个字典树的边权没有任何卵用，因为题目中已经给出边上的$d_{i}$ 了。

其次这个题一眼最短时间，说人话就是最短路，考虑 Dijkstra 求最短路，因为这里 SPFA 显然已死（你真的要卡$O(nm)$？）。问题转化为如何取去建图，根据题意，通过一条边的边权是如下构成的：

$$w_{(u,v)} = c_{(u,v)} + \operatorname{LCP}(d_{now}, d_{i})$$

不难注意到题目中慷慨的给我们了字典树，根据字典树上的性质，任意两个点之间的 LCA 节点的深度大小就是这两点的所构成字符串的最长公共前缀长度，那么边权转化为：

$$w_{(u,v)} = c_{(u,v)} + dep\left\{\operatorname{LCA}(d_{now}, d_{i}\right\}$$

但是这里面有一个棘手的地方就是这个$d_{now}$，因为如果我们真的要在 Dijkstra 上跑的话这个$d_now$ 是不太好处理的。考虑题目的性质，注意到题目中的点几乎没有任何卵用，因为所有信息都在有向图的边上，那么我们考虑怎么从边上下手。考虑点边互换，将边拆成入点和出点，连边$in \to out$，边权为$c_{e}$。让后考虑这个 LCA 怎么处理，其实很简单，我们对于第一个边的出点，我们向第二个边的入点连上边权为两个边上的 LCA 权，即$dep\left\{ \operatorname{LCA}(d_{(u,v)},d_{(v,t)}) \right\}$。

注意到节点$1$ 向哪里走都是无代价的，所以对于所有$1 \to a$ 的边，我们建超级源点$S$，让$S \to a$，边权为$0$ 即可。

让后输出最短路长度的时候，答案即为$\min\limits_{b_{e}=i} dis_{out}$，正确性是显然的。

写完交上去，恭喜你 MLE+TLE。为什么？因为边数最高可到达$O(m^2)$ 啊，这个时候又要开始优化建图了（悲）。

首先原来的$in \to out$ 显然是不能动的，我们考虑对$\operatorname{LCA}$ 上下手，注意到我们对于$\operatorname{LCA}$ 上都是一个一个连边的，而$\operatorname{LCA}$ 对于大多数对节点是相同的，这是什么，虚树啊！我们考虑虚树的大小能否支持我们操作，不妨设$S=\left\{ d_{i}| b_{i}=u,a_{i}=u \right\}$，那么这些边的边权只能是$S$ 中任意两点 LCA 的深度，根据虚树特性理论，$S$，中任意两点的 LCA 总共只有$O(|S|)$ 个，对于所有点，$\sum\limits_{u} |S_u|=m$，边复杂度$O(m)$，可以接受。

我们考虑把 LCA 这个点拿出来建虚点，在子树中的节点连一个 LCA 的虚点，让后在从这个虚点连向另外一个虚点，让后在利用虚树进行建边，但是这样边数是$O(n)$ 的，总边数还是$O(n^2)$ 的，还是会被卡，考虑怎么优化。

注意到，我们实际上连边都是在子树中的节点连一个 LCA 的虚点，让后在从这个虚点连向另外一个虚点，考虑这个怎么优化。子树的性质，DFN连续。那么，问题转化为 DFS 序上的区间向点连边，点向另外一个连续区间连边，这是什么，线段树优化建图啊！让后就做完了，时间复杂度因为连边是$O(\log n)$ 的，所以总复杂度是$O(n \log^2 m)$。

能不能再给力一点啊？

上述过程我们是在暴力枚举 LCA 的，事实上，如果两点间连了一堆的边，但是只有代价最小的边是有用的，剩下都是没太大啥用的，连了也不影响。

我们先把$S$ 集合求出来，连边的话我们从$[1,i]$ 的出点向$[i+1,t]$ 入点，$[i+1,t]$ 出点向$[1,i]$ 入点连边，其中$t=|S|$，这个可以用线段树也可以用神秘的前缀后缀优化建图来做。让后根据上面所说的，只有代价最小的边有用，也就是说对于一个子树区间，只有$\min_{x,y} dep[ \operatorname{lca}(x,y)]$ 才有用，我们考虑这个代价最小的边怎么连，注意到每次都是某个前缀向后缀连边，或者后缀向前缀连边，为什么，你思考上面线段树的做法。那么，我们建立四个数组：前缀入点、前缀出点、后缀入点、后缀出点。这样的建边是$O(1)$ 的，时间复杂度是$O(n \log m)$。

代码为了易懂（同时也是我自己码风 www），一些代码是封装的好进行辨认。

#include<bits/stdc++.h>
#define int long long
#define pir pair<int,int>
using namespace std;
constexpr int MN=1e6+15,MLOG=20;
struct Edge{
    int v,w;
};
struct EDGE{
    int a,b,c,d;
}e[MN];
int n,m,K,S,ans[MN],hlca[MN],ntot,prein[MN],preout[MN],sufin[MN],sufout[MN];
vector<int> out[MN],in[MN];
vector<Edge> adj[MN];
vector<pir> vt; // 这是集合 S

namespace Trie{
    vector<int> g[MN];
    int fa[MN][30],dep[MN],dfn[MN],dfntot;

    void triedfs(int u,int pre){
        dfn[u]=++dfntot;
        fa[u][0]=pre;
        dep[u]=dep[pre]+1;
        for(int i=1;i<=MLOG;i++){
            fa[u][i]=fa[fa[u][i-1]][i-1];
        }
        for(auto v:g[u]){
            triedfs(v,u);
        }
    }

    int lca(int x,int y){
        if(dep[x]>dep[y]) swap(x,y);
        for(int i=MLOG;i>=0;i--){
            if(dep[fa[y][i]]>=dep[x]) y=fa[y][i];
        }
        if(x==y) return x;
        for(int k=MLOG;k>=0;k--){
            if(fa[x][k]!=fa[y][k]){
                x=fa[x][k],y=fa[y][k];
            }
        }
        return fa[x][0];
    }

}using namespace Trie;

namespace Dijkstra{

    int dis[MN];
    bool vis[MN];

    void dijk(int st){
        memset(dis,0x3f,sizeof(dis));
        memset(vis,0,sizeof(vis));
        priority_queue<pir,vector<pir>,greater<pir>> q;
        dis[st]=0;
        q.push(pir(0,st));
        while(!q.empty()){
            int u=q.top().second;
            q.pop();
            if(vis[u]) continue;
            vis[u]=1;
            for(auto e:adj[u]){
                int v=e.v;
                if(dis[v]>dis[u]+e.w){
                    dis[v]=dis[u]+e.w;
                    q.push(pir(dis[v],v));
                }
            }
        }
    }

}using namespace Dijkstra;

bool cmp(pir x,pir y){
    return dfn[x.first]<dfn[y.first];
}

void clear(){
    S=MN-3;
    ntot=dfntot=0;
    memset(dfn,0,sizeof(dfn));
    memset(dep,0,sizeof(dep));
    memset(fa,0,sizeof(fa));
    for(int i=0;i<MN;i++){
        in[i].clear();
        out[i].clear();
        g[i].clear();
        adj[i].clear();
    }
}

void solve(){
    cin>>n>>m>>K;
    clear();
    ntot=m<<1;
    for(int i=1;i<=m;i++){
        cin>>e[i].a>>e[i].b>>e[i].c>>e[i].d;
        out[e[i].a].push_back(i);
        in[e[i].b].push_back(i);
    }
    for(int i=1;i<K;i++){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back(v);
    }
    triedfs(1,0);
    for(int i=1;i<=m;i++){
        adj[i].push_back({i+m,e[i].c});
        if(e[i].a==1) adj[S].push_back({i,0});
    }
    
    // 以上都是常规建边

    for(int i=1;i<=n;i++){
        vt.clear();
        for(auto p:in[i]) vt.push_back(pir(e[p].d,p+m));
        for(auto p:out[i]) vt.push_back(pir(e[p].d,p));
        sort(vt.begin(),vt.end(),cmp);
        for(int j=0;j<vt.size();j++){ //新建前缀后缀节点
            prein[j]=++ntot;
            preout[j]=++ntot;
            sufin[j]=++ntot;
            sufout[j]=++ntot;
        }
        for(int j=0;j+1<vt.size();j++){
            hlca[j]=lca(vt[j].first,vt[j+1].first); // 求出 dfn 排序后的任意两个节点的LCA
            adj[prein[j+1]].push_back({prein[j],0}); // 前缀后缀初始化建图
            adj[preout[j]].push_back({preout[j+1],0});
            adj[sufin[j]].push_back({sufin[j+1],0});
            adj[sufout[j+1]].push_back({sufout[j],0});
        }
        for(int j=0;j<vt.size();j++){
            // 前缀建图要分类，别建炸缸了
            if(vt[j].second<=m){
                adj[sufin[j]].push_back({vt[j].second,0});
                adj[prein[j]].push_back({vt[j].second,0});
            }
            else{
                adj[vt[j].second].push_back({sufout[j],0});
                adj[vt[j].second].push_back({preout[j],0});
            }
        }
        for(int j=0;j+1<vt.size();j++){
            // 连边，这里dep-1是因为根节点dep=1，而lcp是根节点到
            // 当前节点的距离，dep[rt]=1，所以要-1
            adj[sufout[j+1]].push_back({prein[j], dep[hlca[j]]-1});
            adj[preout[j]].push_back({sufin[j+1], dep[hlca[j]]-1});
        }
    }
    dijk(S);
    memset(ans,0x3f,sizeof(ans));
    for(int i=1;i<=m;i++){
        // 暴力枚举
        ans[e[i].b]=min(ans[e[i].b],dis[i+m]);
    }
    for(int i=2;i<=n;i++) cout<<ans[i]<<'\n';
}

signed main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}