[LOJ#2270][BZOJ4912][SDOI2017]天才黑客

试题描述

SD0062 号选手小 Q 同学为了偷到 SDOI7012 的试题，利用高超的黑客技术潜入了 SDOI 出题组的内联网的中央控制系统，然而这个内联网除了配备有中央控制系统，还为内联网中的每条单向网线设定了特殊的通信口令，这里通信口令是一个字符串，不同网线的口令可能不同。这让小 Q 同学感觉有些棘手， 不过这根本难不倒他，很快他就分析出了整个内联网的结构。

内联网中有 n 个节点（从 1 到 n 标号）和 m 条单向网线，中央控制系统在第 1 个节点上，每条网线单向连接内联网中的某两个节点，从 1 号节点出发经过若干条网线总能到达其他任意一个节点。每个节点都可以运行任意的应用程序，应用程序会携带一条通信口令，当且仅当程序的口令与网线的口令相同时，程序才能通过这条网线到达另一端的节点继续运行，并且通过每条网线都需要花费一定的时间。

每个应用程序可以在任意一个节点修改通信口令，修改通信口令花费的时间可以忽略不计，但是为了减小修改量，需要先调用一个子程序来计算当前程序的口令和网线的口令的最长公共前缀（记其长度为 len），由于获取网线的口令的某个字符会比较耗时，调用一次这个子程序需要花费 len 个单位时间。

除此之外，小 Q 同学还在中央控制系统中发现了一个字典，每条网线的口令都是字典中的某个字符串。具体来说，这个字典是一棵 k 个节点（从 1 到 k 标号）的有根树，其中根是第 1 个节点，每条边上有一个字符，字符串 S 在字典中当且仅当存在某个点 u 使得从根节点出发往下走到 u 的这条路径上的字符顺次拼接构成 S。

现在小 Q 同学在 1 号节点同时开启了 $\mathrm{n-1 个应用程序，这些应用程序同时运行且互不干扰，每个程序的通信口令都为空，他希望用最短的时间把这些程序分别发送到其他节点上，你需要帮小\; Q\; 同学分别计算出发送到第 i(=2,3,\dots ,n) 个节点的程序完成任务的最短时间。}$

输入

第一行是一个正整数 T，表示测试数据的组数，

对于每组测试数据，

第一行是三个整数 n，m，k，分别表示内联网的节点数、内联网的网线条数、字典树的节点数，

接下来 m 行，每行包含四个整数 ai​​，bi​​，ci​​, di（1≤ai,bi≤n，0≤ci≤20000，1≤di≤k），表示沿着这条网线可以从第 ai​​ 个节点花费 ci 个单位时间到达第 bi 个节点，网线的口令是由从字典树的根到 di​​ 这个点的路径上的字符顺次拼接构成的字符串（可能为空），需要注意的是这个内联网可能有自环和重边，

接下来 $\mathrm{k-1 行，每行包含三个整数 ui，vi，wi（1\le ui,vi\le k，1\le wi\le 20000），表示字典树上有一条 ui\to vi 的边，边上有字符 wi，保证给出的边构成一棵以 1 为根的有根树，并且每个点连出去的边上的字符互不相同。}$

输出

对于每组测试数据，输出 

$\mathrm{n-1 行，第 i 行表示发送到第 i+1 个节点的程序完成任务的最短时间。}$

输入示例

14 4 61 2 2 52 3 2 52 4 1 64 2 1 61 2 12 3 13 4 14 5 21 6 2

输出示例

273

数据规模及约定

对于 100% 的数据，T≤10，2≤n≤50000，1≤m≤50000，1≤k≤20000，保证满足 n>5000 或 m>5000 的数据不超过 2 组。

题解

这题思路的前半部分挺妙的，后半部分就丧心病狂了。。。

首先考虑暴力，我们可以把原图上的每个边作为新图的节点，这样我们最短路转移的时候就可以方便地知道上一次和这一次在 Trie 树上的 lca。但是暴力连的话显然有 n² 条边，于是考虑优化建图。

先区分好三个名词：原图指输入给出的有向图，Trie 树指的是输入给出的有根树，新图指的是算法新建的图。

对于原图中每个节点，我们把和这个节点相连的边在 Trie 树上的节点拿出来建立一棵虚树。

那么我们就可以轻易的知道以某个节点为 lca 的点对有哪些了，那么在新图中创建两个用虚树 DFS 序表示的线段树，两个线段树分别管原图中的入边和出边（把它们分别称为入线段树和出线段树）。入边在新图中对应的节点向入线段树的叶节点连边，入线段树的节点之间是自底向上连边；出线段树叶节点向新图中对应点连边，出线段数的节点是自上向下连边的。

然后对于虚树上的每个节点 u，以它为 lca 的点对就是所有 u 的两两子树之间连边，那么我们枚举 u 的儿子 son，然后就是这个 son 的子树向 u 的其他儿子的子树连边，注意在 DFS 序中，“son 的子树”是一段区间，“其他儿子的子树”是两段区间，那么就是线段树上的 logn 个区间向 2logn 的区间两两连边，我们可以建一个辅助点，把边数变成 log 而不是 log² 的。除此之外，u 本身需要向它的子树连边，它的子树也要向 u 连边。注意这一段说的连边的权值都是 u 在 Trie 树上的深度。并且提醒一下在建辅助点的时候只需要把入边的权值设成深度，出边不需要再设了，否则在跑最短路时会重复计算这个代价。

这题呀，就是不知不觉就把代码写成 10K 了。。。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;const int BufferSize = 1 << 16;char buffer[BufferSize], *Head, *Tail;inline char Getchar() { if(Head == Tail) { int l = fread(buffer, 1, BufferSize, stdin); Tail = (Head = buffer) + l; } return *Head++;}int read() { int x = 0, f = 1; char c = Getchar(); while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); } while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); } return x * f;}#define maxn 100010#define maxnode 1000010#define maxm 6000380#define maxlog 17#define ool (1ll << 60)#define LL long longnamespace NG { int ToT, val[maxnode]; int iRt[maxn], oRt[maxn]; struct Seg_info { int l, r, lc, rc; Seg_info() {} Seg_info(int _1, int _2, int _3, int _4): l(_1), r(_2), lc(_3), rc(_4) {} } info[maxnode]; int m, head[maxnode], nxt[maxm], to[maxm], dist[maxm]; void init() { ToT = 0; memset(val, 0, sizeof(val)); m = 0; memset(head, 0, sizeof(head)); return ; } void AddEdge(int a, int b, int c) {// printf("NG::AddEdge(%d -> %d : %d)\n", a, b, c); to[++m] = b; dist[m] = c; nxt[m] = head[a]; head[a] = m; return ; } int iseg_node(int o, int pos) { if(info[o].l == info[o].r) return o; int mid = info[o].l + info[o].r >> 1; if(pos <= mid) { if(!info[o].lc) { info[o].lc = ++ToT; info[info[o].lc] = Seg_info(info[o].l, mid, 0, 0); AddEdge(info[o].lc, o, 0); } return iseg_node(info[o].lc, pos); } if(!info[o].rc) { info[o].rc = ++ToT; info[info[o].rc] = Seg_info(mid + 1, info[o].r, 0, 0); AddEdge(info[o].rc, o, 0); } return iseg_node(info[o].rc, pos); } int oseg_node(int o, int pos) { if(info[o].l == info[o].r) return o; int mid = info[o].l + info[o].r >> 1; if(pos <= mid) { if(!info[o].lc) { info[o].lc = ++ToT; info[info[o].lc] = Seg_info(info[o].l, mid, 0, 0); AddEdge(o, info[o].lc, 0); } return oseg_node(info[o].lc, pos); } if(!info[o].rc) { info[o].rc = ++ToT; info[info[o].rc] = Seg_info(mid + 1, info[o].r, 0, 0); AddEdge(o, info[o].rc, 0); } return oseg_node(info[o].rc, pos); } int cIntv, Intv[maxn]; void getintv(int o, int ql, int qr) { if(!o) return ; if(ql <= info[o].l && info[o].r <= qr) Intv[++cIntv] = o; else { int mid = info[o].l + info[o].r >> 1; if(ql <= mid) getintv(info[o].lc, ql, qr); if(qr > mid) getintv(info[o].rc, ql, qr); } return ; } void GetIntv(int o, int ql, int qr) { cIntv = 0; if(ql > qr) return ; getintv(o, ql, qr); return ; } struct Node { int u; LL d; Node() {} Node(int _, LL __): u(_), d(__) {} bool operator < (const Node& t) const { return d > t.d; } }; priority_queue 
            
              Q; bool vis[maxnode]; LL d[maxnode]; void ShortPath(int s) { memset(vis, 0, sizeof(vis)); for(int i = 1; i <= ToT; i++) d[i] = ool; d[s] = 0; Q.push(Node(s, 0)); while(!Q.empty()) { int u = Q.top().u; Q.pop();// printf("(u)%d ", u); if(vis[u]) continue; vis[u] = 1; for(int e = head[u]; e; e = nxt[e]) if(d[to[e]] > d[u] + dist[e] + val[to[e]]) { d[to[e]] = d[u] + dist[e] + val[to[e]]; if(!vis[to[e]]) Q.push(Node(to[e], d[to[e]])); } } return ; }}struct Edge { int from, to, dist, tnode; Edge() {} Edge(int _1, int _2, int _3, int _4): from(_1), to(_2), dist(_3), tnode(_4) {}} es[maxn];struct Graph { int m, hto[maxn], nto[maxn], hfr[maxn], nfr[maxn]; void init() { m = 0; memset(hto, 0, sizeof(hto)); memset(hfr, 0, sizeof(hfr)); return ; } void AddEdge(int a, int b, int c, int d) { es[++m] = Edge(a, b, c, d); nto[m] = hto[a]; hto[a] = m; nfr[m] = hfr[b]; hfr[b] = m; return ; }} G;struct Tree { int n, m, head[maxn], nxt[maxn], to[maxn]; int dep[maxn], Log[maxn<<1], mnp[maxlog][maxn<<1], pos[maxn], clo; void init() { m = 0; memset(head, 0, sizeof(head)); clo = 0; return ; } void AddEdge(int a, int b) { to[++m] = b; nxt[m] = head[a]; head[a] = m; return ; } void build(int u) { mnp[0][++clo] = u; pos[u] = clo; for(int e = head[u]; e; e = nxt[e]) { dep[to[e]] = dep[u] + 1; build(to[e]); mnp[0][++clo] = u; } return ; } void rmq_init() { Log[1] = 0; for(int i = 2; i <= clo; i++) Log[i] = Log[i>>1] + 1; for(int j = 1; (1 << j) <= clo; j++) for(int i = 1; i + (1 << j) - 1 <= clo; i++) { int a = mnp[j-1][i], b = mnp[j-1][i+(1<
             
              < dep[b] ? a : b; } return ; } int lca(int a, int b) { int l = pos[a], r = pos[b]; if(l > r) swap(l, r); int t = Log[r-l+1]; a = mnp[t][l]; b = mnp[t][r-(1<
              
                %d : %d\n", x, NG::Intv[i], tree.dep[u]); } } } NG::GetIntv(oRt, dl[u], dl[u]); if(NG::cIntv) { int x = NG::Intv[1]; NG::GetIntv(iRt, dl[u] + 1, dr[u]); if(NG::cIntv) { for(int i = 1; i <= NG::cIntv; i++) { NG::AddEdge(NG::Intv[i], x, tree.dep[u]);// printf("HERE@@@@@@@ %d -> %d : %d | we are here %d\n", NG::Intv[i], x, tree.dep[u], u); } } } for(int e = head[u]; e; e = nxt[e]) { NG::GetIntv(iRt, dl[to[e]], dr[to[e]]); if(NG::cIntv) { cbuff = NG::cIntv; for(int i = 1; i <= cbuff; i++) buff[i] = NG::Intv[i]; } else continue; int newnode = 0; NG::GetIntv(oRt, dl[u] + 1, dl[to[e]] - 1); if(NG::cIntv) { newnode = ++NG::ToT; for(int i = 1; i <= cbuff; i++) NG::AddEdge(buff[i], newnode, tree.dep[u]); for(int i = 1; i <= NG::cIntv; i++) NG::AddEdge(newnode, NG::Intv[i], 0); } NG::GetIntv(oRt, dr[to[e]] + 1, dr[u]); if(NG::cIntv) { if(newnode) for(int i = 1; i <= NG::cIntv; i++) NG::AddEdge(newnode, NG::Intv[i], 0); else { newnode = ++NG::ToT; for(int i = 1; i <= cbuff; i++) NG::AddEdge(buff[i], newnode, tree.dep[u]); for(int i = 1; i <= NG::cIntv; i++) NG::AddEdge(newnode, NG::Intv[i], 0); } } } /*printf("(u)%d: ", u); for(int e = head[u]; e; e = nxt[e]) printf("%d ", to[e]); printf("to[e] ends\n");*/ for(int e = head[u]; e; e = nxt[e]) AddEdges(to[e]);// printf("return to %d [%d, %d]\n", u, dl[u], dr[u]); return ; } void G_build(int u) { init(); n = ci = co = 0; for(int e = G.hfr[u]; e; e = G.nfr[e]) iN[++ci] = e, nodes[++n] = es[e].tnode; for(int e = G.hto[u]; e; e = G.nto[e]) oN[++co] = e, nodes[++n] = es[e].tnode; if(!ci || !co) return ; sort(nodes + 1, nodes + n + 1, cmp); int t = n; for(int i = 1; i < t; i++) nodes[++n] = tree.lca(nodes[i], nodes[i+1]); sort(nodes + 1, nodes + n + 1, cmp); n = unique(nodes + 1, nodes + n + 1) - nodes - 1; for(int i = 1; i < n; i++) { int a = nodes[i], b = nodes[i+1], c = tree.lca(a, b); AddEdge(c, b, tree.cdist(c, b)); } clo = 0; build(nodes[1]); NG::info[iRt = NG::iRt[u] = ++NG::ToT] = NG::Seg_info(1, clo, 0, 0); NG::info[oRt = NG::oRt[u] = ++NG::ToT] = NG::Seg_info(1, clo, 0, 0);// printf("G_build(%d) %d %d %d\n", u, n, clo, nodes[1]); for(int i = 1; i <= ci; i++) { int u = NG::iseg_node(iRt, dl[es[iN[i]].tnode]); NG::AddEdge(iN[i], u, 0); } for(int i = 1; i <= co; i++) { int u = NG::oseg_node(oRt, dl[es[oN[i]].tnode]); NG::AddEdge(u, oN[i], 0); } AddEdges(nodes[1]); return ; }} vtree;LL Ans[maxn];void work() { G.init(); tree.init(); int n = read(), m = read(), k = read();// printf("%d %d %d\n", n, m, k); for(int i = 1; i <= m; i++) { int a = read(), b = read(), c = read(), d = read(); G.AddEdge(a, b, c, d); } NG::init(); NG::ToT = m; for(int i = 1; i <= G.m; i++) NG::val[i] = es[i].dist; int Start = ++NG::ToT; for(int e = G.hto[1]; e; e = G.nto[e]) NG::AddEdge(Start, e, 0); for(int i = 1; i < k; i++) { int a = read(), b = read(); read(); tree.AddEdge(a, b); } tree.build(1); tree.rmq_init(); for(int i = 1; i <= n; i++) vtree.G_build(i); // printf("ToT: %d %d\n", NG::ToT, NG::m); NG::ShortPath(Start); for(int i = 1; i <= n; i++) Ans[i] = ool; for(int i = 1; i <= G.m; i++) Ans[es[i].to] = min(Ans[es[i].to], NG::d[i]); for(int i = 2; i <= n; i++) printf("%lld\n", Ans[i]); return ;}int main() { int T = read(); while(T--) work(); return 0;}