树剖T 56，求条

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 200100
int n,q,c[N],dis[N],fa[N],son[N],top[N],siz[N],dep[N],lca;
int u,v,w,x,y,ans,mx[N],dfn[N],idx;
struct edge{int nex,val;};
vector<edge>p[N];
struct Segment_tree{int l,r,mx;}tr[N<<2];
void pushup(int now){tr[now].mx=max(tr[now*2].mx,tr[now*2+1].mx);}
void build(int now,int l,int r){
	tr[now].l=l,tr[now].r=r;
	if(l==r){tr[now].mx=mx[l];return;}
	int mid=(l+r)>>1;
	build(now*2,l,mid),build(now*2+1,mid+1,r);
	pushup(now);
}
int query(int now,int l,int r){
	if(tr[now].r<l||r<tr[now].l)return 0;
	if(l<=tr[now].l&&tr[now].r<=r)return tr[now].mx;
	return max(query(now*2,l,r),query(now*2+1,l,r));
}
void dfs1(int x,int fat){
	fa[x]=fat,dep[x]=dep[fat]+1;
	for(auto y:p[x]){
		if(y.nex==fat)continue;
		dis[y.nex]=y.val+dis[x],dfs1(y.nex,x);
		siz[x]+=siz[y.nex];
		if(siz[y.nex]>siz[son[x]])son[x]=y.nex;
	}
}
void dfs2(int x,int fat){
	dfn[x]=++idx;
	if(son[fat]==x)top[x]=top[fat];
	else top[x]=x;
	if(son[x])dfs2(son[x],x);
	for(auto y:p[x]){
		if(y.nex!=fat&&y.nex!=son[x]){
			dfs2(y.nex,x);
		}
	}
}
void dfs3(int x,int father){
	mx[dfn[x]]=c[x];
	for(auto y:p[x]){
		if(y.nex!=father){
			dfs3(y.nex,x);
			mx[dfn[x]]=max(mx[dfn[x]],mx[dfn[y.nex]]-2*y.val);
		}
	}
}
void dfs4(int x,int father){
	for(auto y:p[x]){
		if(y.nex!=father){
			mx[dfn[y.nex]]=max(mx[dfn[y.nex]],mx[dfn[x]]-2*y.val);
			dfs4(y.nex,x);
		}
	}
}
int tree_query(int x,int y){
	int ans=-2e9;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		ans=max(ans,query(1,dfn[top[x]],dfn[x]));
		x=fa[top[x]];
	}
	if(dep[x]<dep[y])lca=x;
	else lca=y;
	ans=max(ans,query(1,min(dfn[x],dfn[y]),max(dfn[x],dfn[y])));
	return ans;
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>c[i];
	for(int i=1;i<n;i++){
		cin>>u>>v>>w;
		p[u].push_back({v,w}),p[v].push_back({u,w});
	}
	dfs1(1,0),dfs2(1,0),dfs3(1,0),dfs4(1,0);
	build(1,1,n);
	while(q--){
		cin>>x>>y;
		int t=tree_query(x,y);
		cout<<c[x]+c[y]-(dis[x]+dis[y]-2*dis[lca])+t<<'\n';
	}
	return 0;
}