同一份代码

开O2版本

没开O2版本

不开O2第15个点RE了

开O2就AC了

按理说不应该是开O2容易RE吗（

代码思路是树剖先求所有路径的路径和，排序后从较长的路径依次加入，若路径和相等则同时加入，求已加入的路径的交中最大值

code

P.S. 把代码最后输出的max改成min能获得sub1里面WA的三个点，感觉也很玄学（按理说这样应该会全WA

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#define int long long
#define ls (x<<1)
#define rs ((x<<1)|1)
#define mid ((l+r)>>1)
#define pc(x) putchar(x)

using namespace std;

inline int read()
{
	int w,f=1;char c;
	while((c=getchar())>'9'||c<'0')
		if(c=='-')f=-1;
	w=c-'0';
	while((c=getchar())>='0'&&c<='9')
		w=w*10+c-'0';
	return w*f;
}

int printt[50],never_use;

inline void print(int x)
{
	if(x==0)
		pc(48);
	if(x<0)
		pc('-'),x=-x;
	while(x)
		printt[++never_use]=x%10,x/=10;
	while(never_use)
		pc(printt[never_use--]+48);
}

const int N=3e5+5;

struct node{
	int v,w,nxt;
}p[2*N];
int head[N],tott;
void add(int u,int v,int w){p[++tott]={v,w,head[u]},head[u]=tott;}

int dfn[N],rnk[N],dep[N],son[N],sz[N],val[N],fa[N],tot;
void dfs1(int u,int faa)
{
	sz[u]=1;
	for(int i=head[u];i;i=p[i].nxt)
	{
		int v=p[i].v,w=p[i].w;
		if(v==faa)
			continue;
		val[v]=w;
		fa[v]=u;
		dep[v]=dep[u]+1;
		dfs1(v,u);
		sz[u]+=sz[v];
		son[u]=sz[son[u]]<sz[v]?v:son[u];
	}
}
int top[N];
void dfs2(int u,int faa,int topp)
{
	dfn[u]=++tot;
	rnk[tot]=u;
	top[u]=topp;
	if(!son[u])
		return;
	dfs2(son[u],u,topp);
	for(int i=head[u];i;i=p[i].nxt)
	{
		int v=p[i].v;
		if(v==faa||v==son[u])
			continue;
		dfs2(v,u,v);
	}
}


int t[4*N],tm[4*N],sum[4*N],tag[4*N];
void pushup(int x){t[x]=max(t[ls],t[rs]),tm[x]=max(t[ls]==t[x]?tm[ls]:-1,t[rs]==t[x]?tm[rs]:-1);}
void pushdown(int x,int l,int r)
{
	t[ls]+=tag[x];
	t[rs]+=tag[x];
	tag[ls]+=tag[x];
	tag[rs]+=tag[x];
	tag[x]=0;
}
void build(int x,int l,int r)
{
	if(l==r)
		tm[x]=sum[x]=val[rnk[l]];
	else
	{
		build(ls,l,mid);
		build(rs,mid+1,r);
		pushup(x);
		sum[x]=sum[ls]+sum[rs];
	}
}
void update(int x,int l,int r,int L,int R)
{
	if(L<=l&&r<=R)
	{
		t[x]++;
		tag[x]++;
		return;
	}
	if(tag[x])pushdown(x,l,r);
	if(L<=mid)
		update(ls,l,mid,L,R);
	if(R>mid)
		update(rs,mid+1,r,L,R);
	pushup(x);
}
int query_sum(int x,int l,int r,int L,int R)
{
//	cout<<l<<" "<<r<<endl;
	if(L<=l&&r<=R)
		return sum[x];
	int tmp=0;
	if(L<=mid)
		tmp+=query_sum(ls,l,mid,L,R);
	if(R>mid)
		tmp+=query_sum(rs,mid+1,r,L,R);
	return tmp;
}

int n;

void update_link(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
		update(1,1,n,dfn[top[x]],dfn[x]);
		x=fa[top[x]];
	}
	if(dep[x]<dep[y])
		swap(x,y);
	if(x!=y)
		update(1,1,n,dfn[y]+1,dfn[x]);
}
int query_link_sum(int x,int y)
{
	int tmp=0;
	while(top[x]!=top[y])
	{
//		cout<<x<<" "<<y<<endl;
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
//		cout<<x<<" "<<dfn[x]<<" "<<top[x]<<" "<<dfn[top[x]]<<endl;
		tmp+=query_sum(1,1,n,dfn[top[x]],dfn[x]);
		x=fa[top[x]];
	}
	if(dep[x]<dep[y])
		swap(x,y);
	if(x!=y)
		tmp+=query_sum(1,1,n,dfn[y]+1,dfn[x]);
	return tmp;
}

struct link{
	int x,y,w;
	bool operator<(link ano)const{
		return w>ano.w;
	}
}L[N];

signed main()
{
	n=read();int m=read();
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read(),w=read();
		add(u,v,w);add(v,u,w);
	}
	dep[1]=1;dfs1(1,0);
	dfs2(1,0,1);
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read();
		L[i]={u,v,query_link_sum(u,v)};
	}
	sort(L+1,L+1+m);
	int ans=0,tmp=0;
	for(int i=1;i<=m;i++)
	{
		tmp=L[i].w;
		while(L[i].w==tmp)
		{
			update_link(L[i].x,L[i].y);
			i++;
		}
		i--;
		if(i!=t[1]||L[1].w-tm[1]>tmp)
			break;
		ans=tm[1];
	}
	print(max(L[1].w-ans,tmp));
	return 0;
}