记录编号	583557	评测结果	AAAAAAAAATTTTTTTTTTT
题目名称	3919.坡伊踹	最终得分	45
用户昵称	zzszscx	是否通过	未通过
代码语言	C++	运行时间	34.076 s
提交时间	2023-10-18 19:53:54	内存使用	49.62 MiB

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const ll N=500009;
ll n,q,u,v,w;
ll a[N],dis[N];
ll Next[N<<1],ver[N<<1],val[N<<1],h[N<<1],cnt=0;
ll fa[N],dep[N],sz[N],son[N];
ll top[N];
void add(ll x,ll y,ll v){
	Next[++cnt]=h[x],ver[cnt]=y,val[cnt]=v,h[x]=cnt;
}

void dfs1(ll x,ll f){
	fa[x]=f,dep[x]=dep[f]+1,sz[x]=1;
	for(ll i=h[x];i;i=Next[i]){
		ll v=ver[i];
		if(v==f) continue;
		dfs1(v,x);
		sz[x]+=sz[v];
		if(sz[son[x]]<sz[v]) son[x]=v;
	}
}

void dfs2(ll x,ll t){
	top[x]=t;
	if(!son[x]) return;
	dfs2(son[x],t);
	for(ll i=h[x];i;i=Next[i]){
		ll v=ver[i];
		if(v==fa[x]||v==son[x]) continue;
		dfs2(v,v);
	}
}

ll LCA(ll x,ll y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		x=fa[top[x]];
	}
	return dep[x]<dep[y]? x:y;
}

void dfs(ll x,ll f){
	for(ll i=h[x];i;i=Next[i]){
		ll v=ver[i];
		if(v==f) continue;
		dis[v]=dis[x]+val[i];
		dfs(v,x);
	}
}

int main(){
	freopen("poitry.in","r",stdin);
	freopen("poitry.out","w",stdout);
	scanf("%lld%lld",&n,&q);
	for(ll i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	for(ll i=1;i<n;i++){
		scanf("%lld%lld%lld",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
	dfs1(1,0);
	dfs2(1,1);
	dfs(1,0);
	ll ans=1e18,x=0;
	while(q--){
		ans=1e18;
		scanf("%lld%lld",&u,&v);
		ll t=LCA(u,v);
		x=u;
		while(x!=t){
			ans=min(ans,max(a[x],dis[u]-dis[x]));
			x=fa[x];
		}
		x=v;
		while(x!=t){
			ans=min(ans,max(a[x],dis[x]-dis[t]+dis[u]-dis[t]));
			x=fa[x];
		}
		ans=min(ans,max(a[t],dis[u]-dis[t]));
		cout<<ans<<endl;
	}
	return 0;
}