提供一个两个 log 的解法，依赖树剖里重链的性质，比较trick：

  1. 求 dp 值 f(以当前点往子树走再回来最多能获取的能量，不包含邻接重儿子)，f1(f2换根后dp值)，f2（以当前点往子树走再回来最多能获取的能量）
  2. 维护重链信息（树状数组维护 f 值）
  3. s->x实际上就是所有重链节点的和（f值和），需要注意3点：
    a.重链底端的整颗子树都可以是答案，不用过滤重儿子
    b.一条重链x跳往另一条重链y时，需要去除另一条重链y对x的统计（x必为y轻儿子，已经统计过答案了，所以要去掉）
    c.最后补上 lca 的父节点作为整颗树的根的dp值（f1），同时去掉x对f1影响即可.
#pragma G++ optimize("Ofast")
#pragma G++ optimize("unroll-loops")
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<functional>
#include<queue>
#include<unordered_map>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<bitset>
#include<random>
#include<iomanip>
#include<numeric>

using namespace std;
using ll=long long;
using ld=long double;
using P=pair<ll,ll>;
const int INF=1e9;
const ll inf=1e18;

struct Fenwick{
	static constexpr int N=1e6+5;
	int n;
	vector<ll>t;
	Fenwick(int x=N):n(x),t(x+5){}
	inline int lowbit(int x){return x&-x;}
	inline void add(int x,ll y)
	{
		for(int i=x;i<=n;i+=lowbit(i))t[i]+=y;
	}
	inline ll query(int x)
	{
		ll res=0;
		for(int i=x;i>=1;i-=lowbit(i))res+=t[i];
		return res;
	}
};

void solve()
{
	int n; cin>>n;
	vector<ll>a(n+1);
	for(int i=1;i<=n;i++)cin>>a[i];

	vector<vector<P>>ed(n+1);
	map<P,int>mp;
	for(int i=1;i<n;i++)
	{
		int x,y,w; cin>>x>>y>>w;
		ed[x].push_back({y,w});
		ed[y].push_back({x,w});
		mp[{x,y}]=mp[{y,x}]=w;
	}

	vector<int>fad(n+1),sz(n+1),son(n+1),dep(n+1);
	vector<int>dfn(n+1),rnk(n+1),top(n+1);
	vector<ll>f(n+1),f1(n+1),f2(n+1),g(n+1);
	Fenwick fen(n+1);
	auto dfs=[&](auto dfs,int x,int fa)->void{
		sz[x]=1;
		fad[x]=fa;
		dep[x]=dep[fa]+1;
		for(auto[y,w]:ed[x])
		{
			if(y==fa)continue;
			g[y]=g[x]+w;
			dfs(dfs,y,x);
			sz[x]+=sz[y];
			f1[x]+=max(0ll,f1[y]-2*w);
			if(sz[son[x]]<sz[y])
			{
				f[x]+=max(0ll,f1[son[x]]-2*mp[{x,son[x]}]);
				son[x]=y;
			}
			else
			{
				f[x]+=max(0ll,f1[y]-2*w);
			}
		}
		f[x]+=a[x];
		f1[x]+=a[x];
		f2[x]=f1[x];
	};
	auto dfs1=[&](auto dfs1,int x,int fa,int tp)->void{
		rnk[dfn[x]=++dfn[0]]=x;
		top[x]=tp;
		fen.add(dfn[x],f[x]);
		if(son[x])dfs1(dfs1,son[x],x,tp);
		for(auto[y,w]:ed[x])
		{
			if(y==fa||y==son[x])continue;
			dfs1(dfs1,y,x,y);
		}
	};
	auto dfs2=[&](auto dfs2,int x,int fa)->void{
		for(auto[y,w]:ed[x])
		{
			if(y==fa)continue;
			f1[y]+=max(0ll,f1[x]-max(0ll,f1[y]-2*w)-2*w);
			dfs2(dfs2,y,x);
		}
	};
	auto LCA=[&](int x,int y)->ll{
		ll res=0;
		while(top[x]!=top[y])
		{
			if(dep[top[x]]<dep[top[y]])swap(x,y);
			res+=max(0ll,f2[son[x]]-2*mp[{x,son[x]}]);
			res+=fen.query(dfn[x])-fen.query(dfn[top[x]]-1);
			res-=g[x]-g[fad[top[x]]];
			int w1=mp[{fad[top[x]],top[x]}];
			res-=max(0ll,f2[top[x]]-2*w1);
			x=fad[top[x]];
		}
		if(dep[x]>dep[y])swap(x,y);
		res+=fen.query(dfn[y])-fen.query(dfn[x]-1);
		res+=max(0ll,f2[son[y]]-2*mp[{y,son[y]}]);
		res-=g[y]-g[x];
		int fa=fad[x],w=mp[{fa,x}];
		res+=max(0ll,f1[fa]-max(0ll,f2[x]-2*w)-2*w);
		return res;
	};

	dfs(dfs,1,0);
	dfs1(dfs1,1,0,1);
	dfs2(dfs2,1,0);

	int q; cin>>q;
	while(q--)
	{
		int s,x; cin>>s>>x;
		cout<<LCA(s,x)<<" ";
	}
	cout<<"\n";
}	

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t=1; cin>>t;
	while(t--)solve();
	return 0;
}