题解

#include<cstdio>
#include<cstring>
#include<algorithm>
#define dd(i) dis[a[i]]+dis[b[i]]-dis[lca[i]]2
using namespace std;
const int maxn=3e5+5;
int top[maxn],fa[maxn],mxson[maxn],siz[maxn],dep[maxn],head[maxn],id[maxn],a[maxn],b[maxn],lca[maxn],dis[maxn],ww[maxn],cf[maxn];
struct sd{
int to,next,w;
}edge[maxn2];
int cnt,n,m,mx1,mx2;
void add(int from,int to,int w1)
{
edge[cnt].to=to;
edge[cnt].next=head[from];
edge[cnt].w=w1;
head[from]=cnt;
}
void dfs(int v,int ff,int deep)
{
id[cnt]=v,fa[v]=ff,dep[v]=deep,siz[v]=1;
int MS=0,MX=0;
for(int i=head[v];i!=0;i=edge[i].next)
{
int to=edge[i].to;
if(to!=ff)
{
ww[to]=edge[i].w;
dis[to]=dis[v]+ww[to];
dfs(to,v,deep+1);
if(MX<siz[to]) MX=siz[to],MS=to;
siz[v]+=siz[to];
}
}
mxson[v]=MS;
}
void dfs2(int v,int tt)
{
top[v]=tt;
if(!mxson[v]) return;
dfs2(mxson[v],tt);
for(int i=head[v];i!=0;i=edge[i].next)
{
if(edge[i].to!=fa[v]&&edge[i].to!=mxson[v])
dfs2(edge[i].to,edge[i].to);
}
}
int LCA(int a,int b)
{
while(top[a]!=top[b])
{
if(dep[top[a]]>dep[top[b]]) a=fa[top[a]];
else b=fa[top[b]];
}
if(dep[a]<dep[b]) return a;
else return b;
}
bool check(int k)
{
memset(cf,0,sizeof(cf)),cnt=0;
for(int i=1;i<=m;i)
if(dd(i)>k) cf[a[i]],cf[b[i]],cf[lca[i]]-=2,cnt;
for(int i=n;i>=1;i--)
{
cf[fa[id[i]]]+=cf[id[i]];
if(ww[id[i]]>=mx2-k&&cf[id[i]]==cnt) return true;
}
return false;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
int a1,b1,w1;
scanf("%d%d%d",&a1,&b1,&w1);
add(a1,b1,w1);add(b1,a1,w1);
mx1=max(mx1,w1);
}
cnt=0,dfs(1,0,1),dfs2(1,1);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a[i],&b[i]);
lca[i]=LCA(a[i],b[i]);
mx2=max(dd(i),mx2);
}
int l=mx2-mx1,r=mx2+1,ans;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid)) r=mid-1,ans=mid;
else l=mid+1;
}
printf("%d",ans);
return 0;
}