不难发现，每一条额外修的路径，会对原树上$(u,v)$路径上的所有边产生贡献
于是这就变成了一个路径修改
那么我们把每一条边赋值到它连接的两个点中深度较大的那个上面，然后每一次用树剖+线段树做路径修改，然后再把权值取回来就行了
几个注意点：
1.记得路径修改的时候$LCA$是不需要改的
2.区间修改要打标记，统计答案之前先把标记全都放掉
3.一个小技巧就是把边从2开始存，这样双向边标号就分别是$(2,3),(4,5)...$，于是每一条双向边的标号除以二都是唯一的，就可以唯一的表示出来
1 //minamoto 2 #include<bits/stdc++.h> 3 #define inf 0x3f3f3f3f 4 using namespace std; 5 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 6 char buf[1<<21],*p1=buf,*p2=buf; 7 template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;} 8 inline int read(){ 9 #define num ch-'0' 10 char ch;bool flag=0;int res; 11 while(!isdigit(ch=getc())) 12 (ch=='-')&&(flag=true); 13 for(res=num;isdigit(ch=getc());res=res*10+num); 14 (flag)&&(res=-res); 15 #undef num 16 return res; 17 } 18 char sr[1<<21],z[20];int C=-1,Z; 19 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} 20 inline void print(int x){ 21 if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x; 22 while(z[++Z]=x%10+48,x/=10); 23 while(sr[++C]=z[Z],--Z);sr[++C]=' '; 24 } 25 const int N=50005; 26 int head[N],ver[N<<1],Next[N<<1],tot=1; 27 inline void add(int u,int v){ 28 ver[++tot]=v,Next[tot]=head[u],head[u]=tot; 29 } 30 int num[N],val[N],bl[N],dfn[N],sz[N],fa[N],dep[N],son[N],top[N],cnt,n,m; 31 void dfs1(int u){ 32 sz[u]=1,dep[u]=dep[fa[u]]+1; 33 for(int i=head[u];i;i=Next[i]){ 34 int v=ver[i]; 35 if(v!=fa[u]){ 36 fa[v]=u,num[v]=i>>1,dfs1(v),sz[u]+=sz[v]; 37 if(sz[son[u]]<sz[v]) son[u]=v; 38 } 39 } 40 } 41 void dfs2(int u,int t){ 42 top[u]=t,dfn[u]=++cnt,bl[cnt]=u; 43 if(son[u]){ 44 dfs2(son[u],t); 45 for(int i=head[u];i;i=Next[i]){ 46 int v=ver[i]; 47 if(v!=fa[u]&&v!=son[u]) dfs2(v,v); 48 } 49 } 50 } 51 int mn[N<<2],tag[N<<2]; 52 #define ls (p<<1) 53 #define rs (p<<1|1) 54 inline void upd(int p){mn[p]=min(mn[ls],mn[rs]);} 55 inline void pd(int p){ 56 if(tag[p]!=inf){ 57 cmin(tag[ls],tag[p]),cmin(tag[rs],tag[p]); 58 cmin(mn[ls],tag[p]),cmin(mn[rs],tag[p]); 59 tag[p]=inf; 60 } 61 } 62 void update(int p,int l,int r,int ql,int qr,int x){ 63 if(ql<=l&&qr>=r) return (void)(cmin(tag[p],x),cmin(mn[p],x)); 64 int mid=(l+r)>>1;pd(p); 65 if(ql<=mid) update(ls,l,mid,ql,qr,x); 66 if(qr>mid) update(rs,mid+1,r,ql,qr,x); 67 upd(p); 68 } 69 void query(int p,int l,int r){ 70 if(l==r) return (void)(val[num[bl[l]]]=mn[p]); 71 int mid=(l+r)>>1;pd(p); 72 query(ls,l,mid),query(rs,mid+1,r); 73 } 74 void change(int u,int v,int x){ 75 while(top[u]!=top[v]){ 76 if(dep[top[u]]<dep[top[v]]) swap(u,v); 77 update(1,1,n,dfn[top[u]],dfn[u],x); 78 u=fa[top[u]]; 79 } 80 if(u==v) return; 81 if(dep[u]<dep[v]) swap(u,v); 82 update(1,1,n,dfn[son[v]],dfn[u],x); 83 } 84 int main(){ 85 // freopen("testdata.in","r",stdin); 86 n=read(),m=read(); 87 for(int i=1,u,v;i<n;++i) 88 u=read(),v=read(),add(u,v),add(v,u); 89 memset(mn,0x3f,sizeof(mn)),memset(tag,0x3f,sizeof(tag)); 90 dfs1(1),dfs2(1,1); 91 while(m--){ 92 int u=read(),v=read(),e=read(); 93 change(u,v,e); 94 } 95 query(1,1,n); 96 for(int i=1;i<n;++i) print(val[i]==inf?-1:val[i]); 97 Ot(); 98 return 0; 99 }