66ptsTLE求助

#include<bits/stdc++.h>
using namespace std;
struct edg{
	int u,v; 
}egs[50010];
vector<int>g[50010];
//------start segtree------
int tag[333333];
struct nod{
	int l,r;
	int mi=0x7f7f7f7f;
}sgt[333333];
nod operator +(const nod&n1,const nod&n2){
	nod ans;
	ans.l=n1.l;
	ans.r=n2.r;
//	cout<<ans.mi<<"->";
	ans.mi=max(n1.mi,n2.mi);
//	cout<<ans.mi<<endl;
	return ans;
}
void psd(int idx){
	int tg=tag[idx];
	tag[idx]=0x7f7f7f7f;
	sgt[idx<<1].mi=min(sgt[idx<<1].mi,tg);
	tag[idx<<1]=min(tag[idx<<1],tg);
	sgt[idx<<1|1].mi=min(sgt[idx<<1|1].mi,tg);
	tag[idx<<1|1]=min(tag[idx<<1|1],tg);
}
void build(int l,int r,int id){
	if(l==r){
		sgt[id].l=sgt[id].r=l;
		return ;
	}
	int mid=(l+r)>>1;
	build(l,mid,id<<1);
	build(mid+1,r,id<<1|1);
	sgt[id]=sgt[id<<1]+sgt[id<<1|1];
}
void modify(int l,int r,int nl,int nr,int id,int v){
	if(nl>nr)swap(nl,nr);
//	cout<<l<<" "<<r<<" "<<nl<<" "<<nr<<endl;
	if(nl<=l&&r<=nr){
//		cout<<"-"<<l<<" "<<r<<" "<<v<<endl;
		sgt[id].mi=min(sgt[id].mi,v);
		tag[id]=min(tag[id],v);
		return ;
	}
	if(l>nr||r<nl)return ;
	psd(id); 
	int mid=(l+r)>>1;
	modify(l,mid,nl,nr,id<<1,v);
	modify(mid+1,r,nl,nr,id<<1|1,v);
	sgt[id]=sgt[id<<1]+sgt[id<<1|1];
}
nod query(int l,int r,int nl,int nr,int id){
	if(nl>nr)swap(nl,nr);
	if(nl<=l&&r<=nr){
		return sgt[id];
	}
	psd(id);
	int mid=(l+r)>>1;
	if(mid>=nr)return query(l,mid,nl,nr,id<<1);
	else if(mid<nl)return query(mid+1,r,nl,nr,id<<1|1);
	else return query(l,mid,nl,nr,id<<1)+query(mid+1,r,nl,nr,id<<1|1);
}
//------end   segtree------
//------start shupou------
int dfn[50010],cn=0;
int top[50010];
int siz[50010];
int dep[50010];
int fu[50010];
void dfs(int u,int fa){
	siz[u]=1;
	dep[u]=dep[fa]+1;
	fu[u]=fa;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==fa)continue;
		dfs(v,u);
		siz[u]+=siz[v];
	}
}
void df2(int u,int fa){
	cn++;
    dfn[u]=cn;
	int mx=0,mxi;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==fa)continue;
		if(siz[v]>mx){
			siz[v]=mx;
			mxi=i;
		}
	}
	if(g[u].size()==0||(u!=1&&g[u].size()==1))return ;
	swap(g[u][mxi],g[u][0]);
	top[g[u][0]]=top[u];
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==fa)continue;
		if(i)top[v]=v;
		df2(v,u);
	}
}
//------end   shupou------
int ans[50010];
int main(){
//	freopen("P4374_11.in","r",stdin);
//	cout<<0x3f3f3f3f<<endl;
	memset(tag,0x7f,sizeof(tag));
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		int p,q;
		scanf("%d%d",&p,&q);
		g[p].push_back(q);
		g[q].push_back(p);
		egs[i].u=p;
		egs[i].v=q;
	}
	dfs(1,1);
	top[1]=1;
	df2(1,1);
//	for(int i=1;i<=n;i++){
//		cout<<dep[i]<<" ";
//	}
//	cout<<endl;
	build(1,n,1);
	while(m--){
		int p,q,r;
		scanf("%d%d%d",&p,&q,&r);
		int cn=0;
		while(top[p]!=top[q]){
			if(dep[top[p]]<dep[top[q]])swap(p,q);
			modify(1,n,dfn[top[p]],dfn[p],1,r);
			p=fu[top[p]];
			cn++;
		}
//		cout<<m<<" "<<cn<<endl;
		if(dep[p]<dep[q])swap(p,q);
		if(p==q)continue;
//		cout<<"("<<q<<" "<<p<<endl;
		modify(1,n,dfn[q]+1,dfn[p],1,r);
	}
	for(int i=1;i<n;i++){
		int u=egs[i].u,v=egs[i].v;
		if(dep[u]<dep[v])swap(v,u);
		int val=query(1,n,dfn[u],dfn[u],1).mi;
		if(val!=0x7f7f7f7f){
			printf("%d\n",val);
		}else{
			printf("-1\n");
		}
	}
	return 0;
}