分析：

树剖裸题，[Usaco2009 Jan]安全路经Travel 的简化版

剖开最短路树，遍历每一条没在最短路树上的边。

这种情况下，有且仅有u到v路径上，出来lca之外的点能够通过这条边到达，并且，路径长度为：dis[u]+dis[v]+val-dis[x];（dis[x]是从根到x的最短路长度，x是路径上除了lca之外的点）

那么，我们考虑这种情况下，需要维护出树上最小值，那么可以用到线段树维护。

附上代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 10005#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define inf 0x3f3f3f3fstruct node{ int to,next,val;}e[N<<1];struct no{ int x,y,z;}a[200000];int head[N],cnt,dep[N],dis[N],fa[N],son[N],siz[N],anc[N],idx[N],tims,minn[N<<2],cov[N<<2],n;void add(int x,int y,int z){ e[cnt].to=y; e[cnt].next=head[x]; e[cnt].val=z; head[x]=cnt++;}void dfs1(int x,int from){ fa[x]=from,siz[x]=1,dep[x]=dep[from]+1; for(int i=head[x];i!=-1;i=e[i].next) { int to1=e[i].to; if(to1!=from) { dis[to1]=dis[x]+e[i].val; dfs1(to1,x); siz[x]+=siz[to1]; if(siz[son[x]]
            
             >1; build(lson); build(rson); PushUp(rt);}void Update(int L,int R,int c,int l,int r,int rt){ if(L<=l&&r<=R) { minn[rt]=min(minn[rt],c); cov[rt]=min(cov[rt],c); return ; } PushDown(rt); int m=(l+r)>>1; if(m>=L)Update(L,R,c,lson); if(m
             
              >1; if(x<=m)return query(x,lson); else return query(x,rson);}void get_lca(int x,int y,int c){ while(anc[x]!=anc[y]) { if(dep[anc[x]]
              
               dep[y])swap(x,y); if(x!=y)Update(idx[x]+1,idx[y],c,1,n,1);}int cnt1;int main(){ int m; memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y,z,op; scanf("%d%d%d%d",&x,&y,&z,&op); if(op) { add(x,y,z); add(y,x,z); } else { a[++cnt1].x=x; a[cnt1].y=y; a[cnt1].z=z; } } dfs1(1,0); dfs2(1,1); build(1,n,1); for(int i=1;i<=cnt1;i++) { int x=a[i].x,y=a[i].y,z=a[i].z; get_lca(x,y,dis[x]+dis[y]+z); } for(int i=2;i<=n;i++) { int t=query(idx[i],1,n,1); if(t==inf)printf("-1 "); else printf("%d ",t-dis[i]); } return 0;}