萌新第一天学c++，求助各位大佬

必须带快读QaQ

c++11 O2 1.72s

树上差分+二分答案

#include <bits/stdc++.h>
using namespace std;
struct edge
{
	int v,w,nxt;
}e[600005]; 
int n,m,u,v,w,pos,lca,l,r,mid,res,cnt,maxn,maxv,acnt,pcnt;
int dis[300005],head[300005],st[300005][25],dep[300005],data[300005][2],ans[300005],d[300005][35],s[300005];
unordered_map<long long,int>ma,id;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
	{
        if(ch=='-')
			f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
	{
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void write(int x)
{
    if(x<0)
	{
    	putchar('-');
		x=-x;
	}
    if(x>9) 
		write(x/10);
    putchar(x%10+'0');
}
inline void addedge(int u,int v,int w)
{
	e[++pos]={v,w,head[u]};
	head[u]=pos;
}
inline void dfs1(int u,int fa=0)
{
	dis[u]=dis[fa]+ma[u*1000000+fa];
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==fa)
			continue;
		dfs1(v,u);
	}
}
inline void dfs2(int u,int fa=0)
{
	st[u][0]=fa;
	dep[u]=dep[fa]+1;
	for(int i=1;i<=__lg(dep[u]);i++)
	{
		st[u][i]=st[st[u][i-1]][i-1];
	} 
	for(int i=head[u];i;i=e[i].nxt)
	{
		if(e[i].v!=fa)
			dfs2(e[i].v,u); 
	}
}
inline int LCA(int u,int v)
{
	if(dep[u]<dep[v])
		swap(u,v);
	while(dep[u]!=dep[v])
	{
		u=st[u][__lg(dep[u]-dep[v])];
	}
	if(u==v)
		return u;
	for(int i=__lg(dep[u]);i>=0;i--)
	{
		if(st[u][i]!=st[v][i])
		{
			u=st[u][i];
			v=st[v][i];
		}
	}
	return st[u][0];
}
inline void dfs3(int u,int fa,int t,int pcnt)
{
	s[u]=d[u][t];
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==fa)
			continue;
		dfs3(v,u,t,pcnt);
		s[u]+=s[v];
		if(s[v]==pcnt)
		{
			acnt++;
			maxv=max(maxv,ma[u*1000000+v]);
		}	
	}
}
inline bool check(int x,int t)
{
	maxn=0,pcnt=0;
	for(int i=1;i<=m;i++)
	{
		if(ans[i]<=x)
			continue;
		maxn=max(maxn,ans[i]);
		pcnt++;
		int u=data[i][0],v=data[i][1];
		d[u][t]++;
		d[v][t]++;
		d[LCA(u,v)][t]-=2;
	}
	acnt=0,maxv=0;	
	dfs3(1,0,t,pcnt);
	if(acnt==0||maxn-maxv>x)
		return false;
	return true;
}
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	n=read();m=read();
	for(int i=1;i<n;i++)
	{
		u=read();v=read();w=read();
		addedge(u,v,w);
		addedge(v,u,w);
		ma[u*1000000+v]=ma[v*1000000+u]=w;
		id[u*1000000+v]=id[v*1000000+u]=i;
	}
	dfs1(1);
	dfs2(1);
	for(int i=1;i<=m;i++)
	{
		u=read();v=read();
		data[i][0]=u,data[i][1]=v;
		lca=LCA(u,v);
		ans[i]=dis[u]+dis[v]-2*dis[lca];
		r=max(r,ans[i]);
	}
	res=r;
	while(l<=r)
	{
		mid=l+r>>1;
		if(check(mid,++cnt))
		{
			res=mid;
			r=mid-1;
		}
		else
			l=mid+1;
	}
	write(res);
	return 0;
}
//Skadi_H