2025-11-25

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define lc (u<<1)
#define rc (u<<1|1)
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fst first
#define sed second
#define Max(a,b) ((a)<(b)?(a)=(b):1)
#define Min(a,b) ((a)>(b)?(a)=(b):1)
using namespace std;
const int N=1e5+10,inf=1e18;
namespace Fread{const int SIZE=1<<21;char buf[SIZE],*S,*T;inline char getchar(){if(S==T){T=(S=buf)+fread(buf,1,SIZE,stdin);if(S==T)return'\n';}return *S++;}}
namespace Fwrite{const int SIZE=1<<21;char buf[SIZE],*S=buf,*T=buf+SIZE;inline void flush(){fwrite(buf,1,S-buf,stdout);S=buf;}
inline void putchar(char c){*S++=c;if(S==T)flush();}struct POPOSSIBLE{~POPOSSIBLE(){flush();}}ztr;}
#define getchar Fread ::getchar
#define putchar Fwrite ::putchar
namespace Fastio{struct Reader{template<typename T>Reader&operator>>(T&x){char c=getchar();T f=1;while (c<'0'||c>'9'){if (c=='-')f=-1;c=getchar();}x=0;while(c>='0'&&c<='9'){x=x*10+(c-'0');c=getchar();}x*=f;return*this;}Reader&operator>>(char&c){c=getchar();while(c==' '||c=='\n')c=getchar();return*this;}Reader&operator>>(char*str){int len=0;char c=getchar();while (c==' '||c=='\n')c=getchar();while(c!=' '&&c!='\n'&&c!='\r'){str[len++]=c;c=getchar();}str[len]='\0';return *this;}Reader&operator>>(string&s){char c=getchar();s.clear();while(c==' '||c=='\n')c=getchar();while(c!=' '&&c!='\n'&&c!='\r'){s+=c;c=getchar();}return*this;}Reader(){}}cin;struct Writer{template<typename T>Writer&operator<<(T x){if(x==0){putchar('0');return *this;}if(x<0){putchar('-');x=-x;}static int sta[45];int top=0;while(x){sta[++top]=x%10;x/=10;}while(top){putchar(sta[top]+'0');--top;}return*this;}Writer&operator<<(char c){putchar(c);return*this;}Writer&operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer(){}}cout;}
#define cin Fastio ::cin
#define cout Fastio ::cout
bool MS;int used,id;
int n,q,L;
int a[N];
int stmax[20][N];
pii st_upper[20][N];
pii st_lower[20][N];
int f[N],g[N];
int h[N];
int ot[N];
vector<int>edge[N];
int son[N];
vector<pii>chain[N]; 
vector<pii>mh[N];
vector<pii>pre[N],suf[N];
vector<int>preh[N],sufh[N];
int st[N],wson[N],deep[N],sz[N],fa[N];
int dept[N];
int dfn[N],rev[N],res;
int lg[N];
inline void merge(pii&u,pii v){
	if(v.fst>u.fst)
	{
		u.sed=u.fst;
		u.fst=v.fst;
	}
	else Max(u.sed,v.fst);
	if(v.sed>u.fst)
	{
		u.sed=u.fst;
		u.fst=v.sed;
	}
	else Max(u.sed,v.sed);
}
void init(){
	res=0;
	memset(f,0,sizeof f);
	memset(g,0,sizeof g);
	memset(h,0,sizeof h);
	memset(ot,0,sizeof ot);
	memset(st,0,sizeof st);
	memset(wson,0,sizeof wson);
	memset(deep,0,sizeof deep);
	memset(sz,0,sizeof sz);
	memset(fa,0,sizeof fa);
	memset(son,0,sizeof son);
	rep(i,1,n)
	{
		edge[i].clear();
		chain[i].clear();
		pre[i].clear();
		suf[i].clear();
		preh[i].clear();
		sufh[i].clear();
		mh[i].clear();
	}
	lg[1]=0;
	rep(i,2,N-1)
	{
		lg[i]=lg[i/2]+1;
	}
}

void dfs1(int u,int fa){
	dept[u]=dept[fa]+a[u];
	deep[u]=deep[fa]+1;
	::fa[u]=fa;
	sz[u]=1;
	pii vl=mp(0,0);
	f[u]=a[u];
	for(auto v:edge[u])
	if(v!=fa)
	{
		dfs1(v,u);
		sz[u]+=sz[v];
		if(sz[v]>sz[wson[u]])
		wson[u]=v;
		Max(f[u],f[v]+a[u]);
		merge(vl,mp(f[v],0));
		Max(h[u],h[v]);
		mh[u].pb(mp(h[v],v));
	}
	Max(h[u],vl.fst+vl.sed+a[u]);
	sort(mh[u].begin(),mh[u].end());
	reverse(mh[u].begin(),mh[u].end());
}
void dfs2(int u,int fa,int st){
	dfn[u]=++res;
	rev[res]=u;
	::st[u]=st;
	int cnt=0;
	for(auto v:edge[u])
	if(v!=fa&&v!=wson[u])
	{
		son[v]=cnt;cnt++;
		pre[u].pb(mp(f[v],0));
		suf[u].pb(mp(f[v],0));
		preh[u].pb(h[v]);
		sufh[u].pb(h[v]);
		chain[u].pb(mp(f[v],v));
	}
	rep(i,1,cnt-1)
	{
		merge(pre[u][i],pre[u][i-1]);
		Max(preh[u][i],preh[u][i-1]);
	}
	per(i,cnt-2,0)
	{
		merge(suf[u][i],suf[u][i+1]);
		Max(sufh[u][i],sufh[u][i+1]);
	}
	if(wson[u])
	{
		int v=wson[u]; 
		g[v]=g[u]+a[u];
		if(suf[u].size())
		Max(g[v],suf[u][0].fst+a[u]);
		chain[u].pb(mp(f[wson[u]],wson[u]));
		dfs2(wson[u],u,st);
	}
	cnt=0;
	for(auto v:edge[u])
	if(v!=fa&&v!=wson[u])
	{
		g[v]=g[u]+a[u];
		if(wson[u])Max(g[v],f[wson[u]]+a[u]);
		if(cnt)						Max(g[v],pre[u][cnt-1].fst+a[u]);
		if(cnt+1<(int)suf[u].size())Max(g[v],suf[u][cnt+1].fst+a[u]);
		dfs2(v,u,v);
		cnt++;
	}
	if(fa)
	chain[u].pb(mp(g[u],fa));
	sort(chain[u].begin(),chain[u].end());
	reverse(chain[u].begin(),chain[u].end());
}
void dfs3(int u,int fa){
	int cnt=0,res=0;
	if(fa)
	{
		for(auto [val,from]:chain[fa])
		{
			if(from!=u)
			{
				cnt++;
				res+=val;
			}
			if(cnt==2)break;
		}
		Max(ot[u],res+a[fa]);
	}
	if(wson[u])
	{
		int v=wson[u]; 
		ot[v]=ot[u];
		if(suf[u].size())
		Max(ot[v],sufh[u][0]);
		dfs3(wson[u],u);
	}
	cnt=0;
	for(auto v:edge[u])
	if(v!=fa&&v!=wson[u])
	{
		ot[v]=ot[u];
		if(wson[u])Max(ot[v],h[wson[u]]);
		if(cnt)						Max(ot[v],preh[u][cnt-1]);
		if(cnt+1<(int)suf[u].size())Max(ot[v],sufh[u][cnt+1]);
		dfs3(v,u);
		cnt++;
	}
}
int LCA,fu,fv;
int lca(int u,int v){
	if(st[u]==st[v])return dfn[u]<dfn[v]?u:v;
	if(deep[st[u]]>deep[st[v]])swap(u,v);
	return lca(u,fa[st[v]]);
}
int getson(int u,int v){
	if(u==v)return u;
	while(1)
	{
		if(st[u]==st[v])return wson[v];
		u=st[u];
		if(fa[u]==v)return u;
		u=fa[u];
	}
}
int query(int l,int r){
	if(l>r)return 0;
	int g=lg[r-l+1];
	return max(stmax[g][l],stmax[g][r-(1<<g)+1]);
}
pii query_upper(int l,int r){
	int g=lg[r-l+1];
	return max(st_upper[g][l],st_upper[g][r-(1<<g)+1]);
}
pii query_lower(int l,int r){
	int g=lg[r-l+1];
	return max(st_lower[g][l],st_lower[g][r-(1<<g)+1]);
}
int solve1(int u,int v,bool tag=0){
	int ans=0;
	if(tag)
	{
		if(!(dfn[u]<=dfn[v]&&dfn[v]<dfn[u]+sz[u]))Max(ans,h[u]);
		if(!(dfn[v]<=dfn[u]&&dfn[u]<dfn[v]+sz[v]))Max(ans,h[v]);
		Max(ans,ot[LCA]);
		int cnt=0,res=0;
		for(auto [val,from]:chain[LCA])
		{
			if(from!=fu&&from!=fv)
			{
				cnt++;
				res+=val;
			}
			if(cnt==2)break;
		}
		for(auto [val,from]:mh[LCA])
		if(from!=fu&&from!=fv)
		{
			Max(ans,val);
			break;
		}
		Max(ans,res+a[LCA]);
	}
	if(st[u]==st[v])
	{
		int l=min(dfn[u],dfn[v]);
		int r=max(dfn[u],dfn[v]);
		l++;r--;
		Max(ans,query(l,r));
		return ans;
	}
	if(deep[st[u]]>deep[st[v]])swap(u,v);
	Max(ans,query(dfn[st[v]],dfn[v]-1));
	int now=fa[st[v]];
	int pos=son[st[v]];
	if(now!=LCA)
	{
		if(wson[now])					Max(ans,h[wson[now]]);
		if(pos)							Max(ans,preh[now][pos-1]);
		if(pos+1<(int)sufh[now].size())	Max(ans,sufh[now][pos+1]);
		pii val=mp(0,0);
		if(pos)					 		merge(val,pre[now][pos-1]);
		if(pos+1<(int)suf[now].size())	merge(val,suf[now][pos+1]);
		merge(val,mp(f[wson[now]],0));
		Max(ans,val.fst+val.sed+a[now]);
	}
	Max(ans,solve1(u,now));
	return ans;
}
int dis(int u,int v){
	if(!v)return 0;
	else if(dfn[v]<=dfn[u]&&dfn[u]<dfn[v]+sz[v])return dept[u]-dept[fa[v]];
	else return dept[u]+dept[v]-dept[LCA]-dept[fa[LCA]];
}
namespace SGT{
	struct vl
	{
		int premax,sufmax,maxn,sum;
		vl operator+(const vl&b)const
		{
			vl c;
			c.premax=max(premax,  sum+b.premax);
			c.sufmax=max(b.sufmax,b.sum+sufmax);
			c.sum=sum+b.sum;
			c.maxn=max({sufmax+b.premax,maxn,b.maxn});
			return c;
		}
	}tre[N<<2];
	void build(int u,int l,int r)
	{
		if(l==r)
		{
			int now=rev[l];
			tre[u].maxn=tre[u].premax=tre[u].sufmax=tre[u].sum=a[now];
			for(auto [w,from]:chain[now])
			{
				if(from==wson[now]||from==fa[now])continue;
				tre[u].maxn=tre[u].premax=tre[u].sufmax=w+a[now];
				break;
			}
			return;
		}
		int mid=(l+r)/2;
		build(lc,l,mid);
		build(rc,mid+1,r);
		tre[u]=tre[lc]+tre[rc];
	}
	vl query(int u,int l,int r,int x,int y)
	{
		if(x<=l&&r<=y)
		{
			return tre[u];
		}
		int mid=(l+r)/2;
		if(x<=mid&&y>mid)return query(lc,l,mid,x,y)+query(rc,mid+1,r,x,y);
		if(x<=mid)return query(lc,l,mid,x,y);
		return query(rc,mid+1,r,x,y);
	}
}using namespace SGT;
int sufmax[N];
vector<pii>opt;
void get_next(int&v,int&pos){
	if(dfn[v]==opt[pos].sed)
	{
		pos++;
		v=rev[opt[pos].fst];
	}
	else
	{
		if(opt[pos].fst<=opt[pos].sed)
		v=rev[dfn[v]+1];
		else
		v=rev[dfn[v]-1];
	}
}
void get_last(int&v,int&pos){
	if(dfn[v]==opt[pos].fst)
	{
		pos--;
		v=rev[opt[pos].sed];
	}
	else
	{
		if(opt[pos].fst<=opt[pos].sed)
		v=rev[dfn[v]-1];
		else
		v=rev[dfn[v]+1];
	}
}
int nxt(int v,int pos){
	if(dfn[v]==opt[pos].sed)
	{
		pos++;
		v=rev[opt[pos].fst];
	}
	else
	{
		if(opt[pos].fst<=opt[pos].sed)
		v=rev[dfn[v]+1];
		else
		v=rev[dfn[v]-1];
	}
	return v;
}
int lst(int v,int pos){
	if(dfn[v]==opt[pos].fst)
	{
		pos--;
		v=rev[opt[pos].sed];
	}
	else
	{
		if(opt[pos].fst<=opt[pos].sed)
		v=rev[dfn[v]-1];
		else
		v=rev[dfn[v]+1];
	}
	return v;
}
int hu,hv;
int val(int x,int pos){
	int nt=(x==hv?0:nxt(x,pos));
	int lt=(x==hu?0:lst(x,pos));
	for(auto [w,from]:chain[x])
	{
		if((x!=hv&&from==nt)||(x!=hu&&from==lt))continue;
		return w+a[x];
	}
	return a[x];
}
int solve2(int u,int v,int w,bool tag=0)
{
	hu=u,hv=v; 
	opt.clear();
	opt.pb(mp(0,0));
	while(1)
	{
		if(u!=LCA)
		opt.pb(mp(dfn[u],dfn[u]));
		if(st[u]==st[LCA])
		{
			if(u!=LCA&&fa[u]!=LCA)
			opt.pb(mp(dfn[u]-1,dfn[LCA]+1));
			break;
		}
		else
		{
			if(u!=st[u])
			opt.pb(mp(dfn[u]-1,dfn[st[u]]));
			u=fa[st[u]];
		}
	}
	opt.pb(mp(dfn[LCA],dfn[LCA]));
	stack<pii>stk;
	
	while(1)
	{
		if(v!=LCA)
		stk.push(mp(dfn[v],dfn[v]));
		if(st[v]==st[LCA])
		{
			if(v!=LCA&&fa[v]!=LCA)
			stk.push(mp(dfn[v]-1,dfn[LCA]+1));
			break;
			v=LCA;
		}
		else
		{
			if(v!=st[v])
			stk.push(mp(dfn[v]-1,dfn[st[v]]));
			v=fa[st[v]];
		}
	}
	while(stk.size())
	{
		swap(stk.top().fst,stk.top().sed);
		opt.pb(stk.top());
		stk.pop();
	}
	u=hu;v=hv;
	int ans=0;
	int pos=opt.size()-1;
	while(v&&dis(u,lst(v,pos))-a[u]>dis(u,hv)-dis(u,v)+w)
	{
		if(v==hv)sufmax[v]=val(v,pos)+dis(u,hv)-dis(u,v)+w;
		else sufmax[v]=max(sufmax[nxt(v,pos)],val(v,pos)+dis(u,hv)-dis(u,v)+w);
		get_last(v,pos);
	}
	deque<pii>d;
	int now=u,pn=1;
	int cnt=0;
	int kkk;
	while(1)
	{
		kkk=val(now,pn)+dis(u,lst(now,pn));
		while(d.size()&&val(d.back().fst,d.back().sed)+dis(u,lst(d.back().fst,d.back().sed))<=kkk)
		d.pop_back();
		d.push_back(mp(now,pn));
		if(now==v)break;
		get_next(now,pn);
		cnt++;
		if(cnt==L)
		{
			rep(i,pn,pos)
			{
				int nw;
				if(opt[i].fst==opt[i].sed)
				{
					nw=rev[opt[i].fst];
				}
				else
				{
					int l=opt[i].fst;
					int r=opt[i].sed;
					if(i==pn)l=dfn[now];
					if(i==pos)r=dfn[v];
					pii vl;
					if(l<r)
					{
						vl=query_upper(l,r);
						vl.fst+=dept[u]-dept[LCA]-dept[fa[LCA]];
					}
					else
					{
						vl=query_lower(r,l);
						vl.fst+=dept[u];
					}
					nw=vl.sed;
				}
				kkk=val(nw,i)+dis(u,lst(nw,i));
				while(d.size()&&val(d.back().fst,d.back().sed)+dis(u,lst(d.back().fst,d.back().sed))<=kkk)
				d.pop_back();
				d.push_back(mp(nw,i));
			}
			
			break;
		}
	}
	now=u,pn=1;
	while(1)
	{
		if(d.front().fst==now)d.pop_front();
		while(v!=hv&&dis(u,v)-dis(u,now)<=dis(u,lst(now,pn))+dis(u,hv)-dis(u,nxt(v,pos))+w)
		{
			get_next(v,pos);
			kkk=val(v,pos)+dis(u,lst(v,pos));
			while(d.size()&&val(d.back().fst,d.back().sed)+dis(u,lst(d.back().fst,d.back().sed))<=kkk)
			d.pop_back();
			d.push_back(mp(v,pos));
		}
		if(d.size())Max(ans,val(now,pn)+val(d.front().fst,d.front().sed)+dis(u,lst(d.front().fst,d.front().sed))-dis(u,now));
		if(v!=hv)Max(ans,sufmax[nxt(v,pos)]+val(now,pn)+dis(u,lst(now,pn)));
		else
		{
			get_next(now,pn);
			vl base=vl{0,0,0,0};

			rep(i,pn,pos)
			{
				if(opt[i].sed==opt[i].fst)
				{
					int kk=val(rev[opt[i].sed],i);
					base=base+vl{kk,kk,kk,a[rev[opt[i].sed]]};
				}
				else if(opt[i].fst<opt[i].sed)
				{
					if(pn==i)
					base=base+query(1,1,n,max(opt[i].fst,dfn[now]),opt[i].sed);
					else
					base=base+query(1,1,n,opt[i].fst,opt[i].sed);
				}
				else
				{
					vl g;
					if(pn==i)
					g=query(1,1,n,opt[i].sed,min(opt[i].fst,dfn[now]));
					else
					g=query(1,1,n,opt[i].sed,opt[i].fst);
					swap(g.premax,g.sufmax);
					base=base+g;
				}
			}
			Max(ans,base.maxn);
			break; 
		}
		if(now==hv)break;
		get_next(now,pn);
	}
	return ans;
}
void solve()
{
	init();
	cin>>n>>q>>L;
	rep(i,1,n)
	cin>>a[i];
	rep(i,2,n)
	{
		int u,v;
		cin>>u>>v;
		edge[u].pb(v);
		edge[v].pb(u);
	}
	dfs1(1,0);
	dfs2(1,0,1);
	dfs3(1,0);
	rep(i,1,n)
	{
		int u=rev[i];
		stmax[0][i]=0;
		if(suf[u].size())
		{
			Max(stmax[0][i],sufh[u][0]);
			Max(stmax[0][i],suf[u][0].fst+suf[u][0].sed+a[u]);
		}
		int vl=a[u];
		for(auto [w,from]:chain[u])
		{
			if(from==wson[u]||from==fa[u])continue;
			vl=w+a[u];
			break;
		}
		st_upper[0][i]=mp(vl+dept[fa[u]],u);
		st_lower[0][i]=mp(vl-dept[u],u);
	}
	rep(w,1,19)
	rep(i,1,n-(1<<w)+1)
	{
		stmax	[w][i]=max(	  stmax[w-1][i],   stmax[w-1][i+(1<<(w-1))]);
		st_upper[w][i]=max(st_upper[w-1][i],st_upper[w-1][i+(1<<(w-1))]);
		st_lower[w][i]=max(st_lower[w-1][i],st_lower[w-1][i+(1<<(w-1))]);
	}
	build(1,1,n);
	id++;
	while(q--)
	{
		int u,v,w;
		cin>>u>>v>>w;
		LCA=lca(u,v);
		fu=getson(u,LCA),fv=getson(v,LCA); 
		int val1=solve1(u,v,1);
		int val2=solve2(u,v,w);
		cout<<max(val1,val2)<<'\n';
	}
}
bool MT; 
signed main()
{
	freopen("path.in","r",stdin);
	freopen("path.out","w",stdout);
	int T=1;
	cin>>T;
	while(T--)
	solve();
	cerr<<"Memory:"<<(&MS-&MT)/1048576.0<<"MB Time:"<<clock()<<"ms\n";
}