建立新图，原图中每条边在新图中是点，点权为$w_i$，边权为两个字符串的LCP。

对字典树进行DFS，将每个点周围一圈边对应的字符串按DFS序从小到大排序。

根据后缀数组利用height数组求LCP的原理，类似地可以得到：

令$h_i=LCP(str_i,str_{i+1})$，则$LCP(str_l,str_r)=\min(h_{l..r-1})$。

枚举每个$h_i$作为分界线，那么新图中两侧的点均可以通过不超过$h_i$的代价互相访问。

建立一排前缀虚点和后缀虚点然后对应前后缀之间连边即可。

如此建图的点数和边数均为$O(m)$，时间复杂度$O(m\log m)$。

 

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef pair
         
          P;const int N=50010,inf=~0U>>1;int Case,n,m,K,i,j,x,y,z,g[N],nxt[N],size[N],f[N],d[N],son[N],loc[N],top[N],dfn;int gi[N],go[N],V[N<<1],NXT[N<<1],ED;int cnt,pi[N<<1],po[N<<1],si[N<<1],so[N<<1],cq,q[N<<1];inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}struct E{int a,b,c,d;}e[N];namespace G{const int N=450010,M=800010;int g[N],v[M],w[M],nxt[M],ed,val[N],d[N];priority_queue
          
           
,greater
           
 >q;inline void add(int x,int y,int z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;}inline void ext(int x,int y){ y+=val[x]; if(y
            
             t.first)continue; for(i=g[t.second];i;i=nxt[i])ext(v[i],t.first+w[i]); }}}inline bool cmp(int x,int y){return loc[e[abs(x)].d]
             
              size[son[x]])son[x]=i; }}void dfs2(int x,int y){ loc[x]=++dfn;top[x]=y; if(son[x])dfs2(son[x],y); for(int i=g[x];i;i=nxt[i])if(i!=son[x])dfs2(i,i);}inline int lca(int x,int y){ for(;top[x]!=top[y];x=f[top[x]])if(d[top[x]]
              
               1){ G::add(pi[i-1],pi[i],0); G::add(po[i-1],po[i],0); G::add(si[i],si[i-1],0); G::add(so[i],so[i-1],0); } if(q[i]>0)G::add(q[i],pi[i],0),G::add(q[i],si[i],0); else q[i]*=-1,G::add(po[i],q[i],0),G::add(so[i],q[i],0); } for(i=1;i