#P3783. [SDOI2017] 天才黑客

    ID: 4811 远端评测题 2000~3000ms 500MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>字符串2017线段树各省省选山东O2优化虚树字典树,Trie 树

[SDOI2017] 天才黑客

题目背景

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

题目描述

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

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

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

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

输入格式

第一行是一个正整数TT,表示测试数据的组数,

对于每组测试数据,第一行是三个整数nn , mm , kk,分别表示内联网的节点数、内联网的网线条数、字典树的节点数,

接下来mm行,每行包含四个整数$a_i,b_i,c_i,d_i(1 \leq a_i,b_i \leq n , 0 \leq c_i \leq 20000 , 1 \leq d_i \leq k)$,表示沿着这条网线可以从第aia_i个节点花费cic_i个单位时间到达第bib_i个节点,网线的口令是由从字典树的根到did_i这个点的路径上的字符顺次拼接构成的字符串(可能为空),需要注意的是这个内联网可能有自环和重边,

接下来k1k-1行,每行包含三个整数$u_i,v_i,w_i(1 \leq u_i,v_i \leq k , 1 \leq w_i \leq 20000)$,表示字典树上有一条uiviu_i \rightarrow v_i的边,边上有字符wiw_i,保证给出的边构成一棵以11为根的有根树,并且每个点连出去的边上的字符互不相同。

输出格式

对于每组测试数据,输出n1n-1行,第ii行表示发送到第i+1i+1个节点的程序完成任务的最短时间。

1
4 4 6
1 2 2 5
2 3 2 5
2 4 1 6
4 2 1 6
1 2 1
2 3 1
3 4 1
4 5 2
1 6 2
2
7
3

提示

【样例解释】

对于样例,从1133的一条可行路径是1231 \rightarrow 2 \rightarrow 3,所需时间是$(2 + lcp(``" , ``1112")) + (2 +lcp(``1112" ,``1112")) = 8$,但这条路径不是最优的,最优路径是$1 \rightarrow 2 \rightarrow 4 \rightarrow 2 \rightarrow 3$,

对于100%100\%的数据T10T \leq 102n500002 \leq n \leq 500001m500001 \leq m \leq 500001k200001 \leq k \leq 20000,保证满足n>5000n>5000m>5000m > 5000的数据不超过22组。