TLE on #13

#include<bits/stdc++.h>
using namespace std;
int si,n,m,ans=1e9+10,sum[300010],Fa[300010][20],a[300010],car[300010][2],d[300010],cnt[300010],t[300010];
struct node{
	int y,z;
};
vector<node>v[300010];
map<pair<int,int>,int>fa;
void dfs(int x,int Fat,int s){
	d[x]=d[Fat]+1;
	Fa[x][0]=Fat;
	for(int i=0;i<v[x].size();i++){
		int y=v[x][i].y;
		if(y==Fat)
			a[x]=v[x][i].z;
	}
	sum[x]=s+a[x];
	for(int i=0;i<v[x].size();i++){
		int y=v[x][i].y;
		if(y!=Fat)
			dfs(y,x,s+a[x]);
	}
}
void lca(){
	for(int i=1;i<=18;i++)
		for(int j=1;j<=n;j++)
			Fa[j][i]=Fa[Fa[j][i-1]][i-1];
}
int query(int x,int y){
	if(d[x]<d[y])
		swap(x,y);
	for(int i=18;i>=0;i--)
		if(d[Fa[x][i]]>=d[y])
			x=Fa[x][i];
	if(x==y)
		return x;
	for(int i=18;i>=0;i--)
		if(Fa[x][i]!=Fa[y][i])
			x=Fa[x][i],y=Fa[y][i];
	return Fa[x][0];
}
void calc(int x,int fat){
	for(int i=0;i<v[x].size();i++){
		int y=v[x][i].y;
		if(y!=fat)
			calc(y,x),cnt[x]+=cnt[y];
	}
}
int work(int x,int y){
	int tmp=0,fat=fa[make_pair(x,y)];
	while(x!=fat){
		if(cnt[x]==si)
			tmp=max(tmp,a[x]);
		x=Fa[x][0];
	}
	while(y!=fat){
		if(cnt[y]==si)
			tmp=max(tmp,a[y]);
		y=Fa[y][0];
	}
	return tmp;
}
bool check(int c){
	si=0;
	int awa=0,id;
	for(int i=1;i<=n;i++)
		cnt[i]=0;
	for(int i=1;i<=m;i++){
		if(t[i]>c){
			si++;
			if(awa<t[i])
				awa=t[i],id=i;
			cnt[car[i][0]]++,cnt[car[i][1]]++,cnt[fa[make_pair(car[i][0],car[i][1])]]-=2;
		}
	}
	if(!awa)
		return true;
	calc(1,0);
//	cout<<awa<<"\n";
	int qwq=work(car[id][0],car[id][1]);
//	cout<<qwq<<"\n";
	if(awa-qwq<=c)
		return true;
	return false;
}
int main(){
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<n;i++){
		int x,y,z;
		cin>>x>>y>>z;
		v[x].push_back({y,z}),v[y].push_back({x,z});
	}
	dfs(1,0,0);
//	
//	cout<<"\n";
//	for(int i=1;i<=n;i++)
//		cout<<a[i]<<" ";
//	cout<<"\n";
//	cout<<"\n";
//	for(int i=1;i<=n;i++)
//		cout<<sum[i]<<" ";
//	cout<<"\n";
	lca();
	for(int i=1;i<=m;i++){
		cin>>car[i][0]>>car[i][1];
		fa[make_pair(car[i][0],car[i][1])]=query(car[i][0],car[i][1]);
		int x=car[i][0],y=car[i][1],fat=fa[make_pair(x,y)];
//		cout<<fat<<"\n";
		int tmp=sum[x]+sum[y]-sum[fat]*2;
		t[i]=tmp;
	}
//	cout<<'\n';
//	for(int i=1;i<=m;i++){
//		cout<<t[i]<<" ";
//	}
//	cout<<"\n";
	int l=0,r=3e8+10;
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid)){
			ans=min(ans,mid);
			r=mid-1;
		}
		else
			l=mid+1;
	}
	cout<<ans;
	return 0;
}