RT,TLE on #9, #16~25, 全部2.20s, 剩下的都AC了

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int sum = 0, f = 1;
	char ch = getchar();
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -f;
	for(; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
	return sum * f;
}
inline void write(int x){
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar('0' + x % 10);
	return;
}
const int N = 2e5 + 10;
int n, q, c[N], dis[N];
struct edge{
	int v, w, nx;
}e[N << 1];
int tot, h[N];
int dft, fa[N], dep[N], sz[N], max_son[N], top[N], idx[N], dfn[N];
int mx[N << 2]; 
void add(int u, int v, int w){
	++ tot;
	e[tot].v = v;
	e[tot].w = w;
	e[tot].nx = h[u];
	h[u] = tot;
	return;
}
namespace DP{
	int f[N];
	void dfs1(int u, int fa){
		f[u] = c[u];
		for(int i = h[u], v, w; i; i = e[i].nx){
			v = e[i].v, w = e[i].w;
			if(v == fa) continue;
			dfs1(v, u);
			f[u] = max(f[u], f[v] - w * 2);
		}
		return;
	}
	void dfs2(int u, int fa){
		for(int i = h[u], v, w; i; i = e[i].nx){
			v = e[i].v, w = e[i].w;
			if(v == fa) continue;
			f[v] = max(f[v], f[u] - w * 2);
			dfs2(v, u);
		}
		return;
	}
	void solve(){
		dfs1(1, 0);
		dfs2(1, 0);
		return;
	}
}
void dfs1(int u, int f){
	fa[u] = f;
	dep[u] = dep[f] + 1;
	sz[u] = 1;
	int maxn = 0;
	for(int i = h[u], v, w; i; i = e[i].nx){
		v = e[i].v, w = e[i].w;
		if(v == f) continue;
		dis[v] = dis[u] + w;
		dfs1(v, u);
		sz[u] += sz[v];
		if(maxn > sz[v]) maxn = sz[v], max_son[u] = v;
	}
	return;
}
void dfs2(int u, int topf){
	++ dft;
	top[u] = topf;
	dfn[u] = dft;
	idx[dft] = u;
	if(max_son[u]) dfs2(max_son[u], topf);
	for(int i = h[u], v; i; i = e[i].nx){
		v = e[i].v;
		if(v == fa[u] || v == max_son[u]) continue;
		dfs2(v, v); 
	}
	return;
}
void push_up(int p){
	mx[p] = max(mx[p << 1], mx[p << 1 | 1]);
	return;
}
void build(int p, int l, int r){
	if(l == r){
		mx[p] = DP :: f[idx[l]];
		return; 
	}
	int mid = l + r >> 1;
	build(p << 1, l, mid);
	build(p << 1 | 1, mid + 1, r);
	push_up(p);
	return;
}
int query(int p, int l, int r, int x, int y){
	if(y < l || r < x) return -1e18;
	if(x <= l && r <= y) return mx[p];
	int mid = l + r >> 1;
	return max(query(p << 1, l, mid, x, y), query(p << 1 | 1, mid + 1, r, x, y)); 
}
int Lca(int u, int v){
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]]) swap(u, v);
		u = fa[top[u]];
	}
	if(dep[u] > dep[v]) swap(u, v);
	return u; 
}
int queryRoute(int u, int v){
	int res = -1e18;
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]]) swap(u, v);
		res = max(res, query(1, 1, n, dfn[top[u]], dfn[u]));
		u = fa[top[u]];
	}
	if(dep[u] > dep[v]) swap(u, v);
	res = max(res, query(1, 1, n, dfn[u], dfn[v]));
	return res;
}
signed main(){
	n = read(), q = read();
	for(int i = 1; i <= n; ++ i) c[i] = read();
	for(int i = 1, u, v, w; i < n; ++ i){
		u = read(), v = read(), w = read();
		add(u, v, w);
		add(v, u, w);
	}
	DP :: solve();
	dfs1(1, 0);
	dfs2(1, 0);
	build(1, 1, n);
	int res, u, v;
	while(q --){
		u = read(), v = read();
		res = c[u] + c[v] + queryRoute(u, v) - (dis[u] + dis[v] - dis[Lca(u, v)] * 2);
		write(res);
		puts("");
	}
	return 0;
}