3783

题面传送门 为啥大家都写两个 log 的线段树优化建边啊，神秘，这 1log 做法好想又好写捏。 首先显然是可以把边看成点的，这样会变成 \(O(m)\) 个点和 \(O(m^2)\) 条边，寄。 但是还没有完全寄掉，我们发现，对于原图的每个点，对于第一个跑到这个点的边暴力转移，剩下的边转移只有一个 ......

题意 传送门 给定一张有向图，每条边上有一个边权以及一个字符串。 一条有向路径的长度为这条路径上每条边的边权之和+按照路径的顺序将这些边上的字符串排成一列，相邻两个串的 $\text{lcp}$ 长度之和。 求 $1$ 号点到其他店的最短路。 用所有边上的字符串构造字典树，保证其大小 $\le 2\ ......