全WA

设第一场演讲 x ，第三场演讲 y

思路：分别考虑第二场演讲在：

• x 到 y 的路径上
• x的子树内
• y的子树内
• LCA(x,y) 以外

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAX=4e5+5;
int n,q,tot,head[MAX],nxt[MAX],ver[MAX],edge[MAX];
int f[MAX][25],dep[MAX],c[MAX],g[MAX][25];
long long d[MAX][25],p[MAX],e[MAX],cnt,c0;
/*
f[i][j]表示i往上走2^j步，到达的位置 
g[i][j]表示i往上走2^j步，最大的c[i] 
d[i][j]表示i网上走2^j步的距离 
p[i]表示i子树内c[i]-2*d(j,i)的最大值
e[i]表示i外c[i]-2*d(j,i)的最大值 
cnt记录x到y的路径长度
c0记录x到y路径上最大的c[i] 
*/
void add(int x,int y,int z){
	nxt[++tot]=head[x],head[x]=tot,ver[tot]=y,edge[tot]=z;
}
void dfs(int x){
	g[x][0]=max(c[x],c[f[x][0]]);
	for(int i=1;i<=log2(dep[x]);i++){
		int t=f[x][i-1];
		f[x][i]=f[t][i-1];
		g[x][i]=max(g[x][i-1],g[t][i-1]);
		d[x][i]=d[x][i-1]+d[t][i-1];
	}
	for(int i=head[x];i;i=nxt[i]){
		int y=ver[i],z=edge[i];
		if(dep[y])continue;
		f[y][0]=x,d[y][0]=z,dep[y]=dep[x]+1;
		dfs(y);
	}
}
int lca(int x,int y){
	cnt=0,c0=c[x];
	if(dep[x]<dep[y])swap(x,y);
	int t=dep[x]-dep[y];
	for(int i=0;i<=log2(t);i++){
		if(t&(1<<i))x=f[x][i],cnt+=d[x][i],c0=max(c0,(long long)g[x][i]);
	}
	if(x==y)return x;
	int l=dep[x];
	for(int i=log2(l);i>=0;i--){
		if(f[x][i]!=f[y][i]){
			x=f[x][i],y=f[y][i];
			cnt+=d[x][i]+d[y][i];
			c0=max(c0,(long long)max(g[x][i],g[y][i]));
		}
	}
	cnt+=d[x][0]+d[y][0];
	c0=max(c0,(long long)max(g[x][0],g[y][0]));
	return f[x][0];
}
void hg(int x){
	e[x]=max(e[x],(long long)c[x]);
	long long s1=0,s2=0;
	for(int i=head[x];i;i=nxt[i]){
		int y=ver[i],z=edge[i];
		if(dep[y]<dep[x])continue;
		if(p[y]-2*z>s1)s2=s1,s1=p[y]-2*z;
		else if(p[y]-2*z>s2)s2=p[y]-2*z;
	}
	for(int i=head[x];i;i=nxt[i]){
		int y=ver[i],z=edge[i];
		if(dep[y]<dep[x])continue;
		if(p[y]==s1)e[y]=max(e[x],s2)-z*2;
		else e[y]=max(e[x],s1)-z*2;
		hg(y);
	}
}
void dp(int x){
	p[x]=c[x];
	for(int i=head[x];i;i=nxt[i]){
		int y=ver[i],z=edge[i];
		if(dep[y]<dep[x])continue;
		dp(y);
		p[x]=max(p[x],p[y]-2*z);
	}
}
signed main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>c[i];
	for(int i=1;i<n;i++){
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
		add(y,x,z);
	}
	dep[1]=1;
	dfs(1);
	dp(1);
	hg(1);
	while(q--){
		long long x,y,ans;
		cin>>x>>y;
		int t=lca(x,y);
		ans=c[x]+c[y]+max(c0,max(max(p[x],p[y]),e[t]))-cnt;
		cout<<ans<<endl;
	}
	return 0;
}