复杂度应该是对的，如果你知道我哪里常数可以大优化（不管需要多么复杂的重构），你都可以提出来。

#include <bits/stdc++.h>
#define ll long long
#define uint unsigned int
#define wr(x,ch) write(x),putchar(ch)
#define pcnt(x) __builtin_popcount(x)
#define plst(x) __builtin_ctz(x)
using namespace std;
int Tim=0;
namespace IO{//by cyffff
	int len=0;
	#define gh() getchar()
	inline int read(){
		char ch=gh();
		int x=0;
		char t=0;
		while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
		while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
		return t?-x:x;
	}
	template<class T>inline void write(T x){
		if(x<0)putchar('-'),x=-x;
		if(x>9)write(x/10);
		putchar(x%10^48);
	}
}
using IO::read;
using IO::write;
const uint N=100005,TMP1=(1u<<5)-1,TMP2=-1;
int a[N],A[N],Ans[N],ans,aans,n,m,x,u,v,s,L[N],R[N],idx[N],rt[N],rt2[N],fa1[N],fa2[N],flag[N],pl,pr,l,r;
ll tim;
int bls;
struct query {
	int l,r,id;
	bool operator<(const query &p) const {
		return idx[l]==idx[p.l]?r<p.r:l<p.l;
	}
}p[N];
vector<int> G[N],vec;
struct Canc {
	int x,y;
}canc[N];int ccnt;
struct node1 {
	uint ch[10],op,s;
}tr[N];int cnt1;
struct node2 {
	uint c[32],op,s;
}tr2[N*2];int sta[N],top,cnt2;
int new1() { 
	++cnt1;
	tr[cnt1].s=0;
	int t=0;
	while(tr[cnt1].op) {
		tim++;
		t=plst(tr[cnt1].op);
		tr[cnt1].ch[t]=0;
		tr[cnt1].op^=(1u<<t);
	}
	return cnt1;
}
int new2() {
	int t,T;
	if(top) t=sta[top--];
	else t=++cnt2;
	while(tr2[t].op) {
		tim++;
		T=plst(tr2[t].op);
		tr2[t].c[T]=0;
		tr2[t].op^=(1u<<T);
	}
	tr2[t].s=0;
	return t;
}
void ins(int p,int x) {
	int t=tr[p].ch[x>>10]=new2();
	tr[p].op|=(1u<<(x>>10));
	tr2[t].op|=(1u<<(x>>5&TMP1));
	tr2[t].c[x>>5&TMP1]|=(1u<<(x&TMP1));
	tr[p].s=tr2[t].s=1;
	return ;
}
int get(int x,int *fa) {
	return x==fa[x]?x:fa[x]=get(fa[x],fa);
}
void merge(int p,int q,int o) {
	int t=tr[p].op&tr[q].op,t2=tr[q].op^t,t3,t4,t5,t6,t7,t8;
	tr[p].op|=t2;
	while(t2) {
		tim++;
		t3=plst(t2);
		if(o) t4=new2(),tr2[t4]=tr2[tr[q].ch[t3]];
		else t4=tr[q].ch[t3];
		tr[p].ch[t3]=t4;
		tr[p].s+=tr2[t4].s;
		t2^=(1u<<t3);
	}
	while(t) {
		tim++;
		t3=plst(t);
		t4=tr[p].ch[t3],t5=tr[q].ch[t3];
		tr[p].s-=tr2[t4].s;
		tr2[t4].s+=tr2[t5].s;
		t6=tr2[t4].op&tr2[t5].op,t7=tr2[t5].op^t6;
		t^=(1u<<t3);
		while(t7) {
			tim++;
			t8=plst(t7);
			tr2[t4].op|=(1u<<t8);
			tr2[t4].c[t8]=tr2[t5].c[t8];
			t7^=(1u<<t8);
		}
		while(t6) {
			tim++;
			t8=plst(t6);
			tr2[t4].s-=(pcnt(tr2[t4].c[t8]&tr2[t5].c[t8])<<1);
			tr2[t4].c[t8]^=tr2[t5].c[t8];
			if(!tr2[t4].c[t8]) tr2[t4].op&=((TMP2)^(1u<<t8));
			t6^=(1u<<t8);
		}
		if(tr2[t4].s) tr[p].s+=tr2[t4].s;
		else tr[p].op&=((TMP2)^(1u<<t3)),tr[p].ch[t3]=0,sta[++top]=t4;
	}
	return ;
} 
int main() {
// 	freopen("data.in","r",stdin);
// 	freopen("data.out","w",stdout);
	n=read(),m=read(),x=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<n;i++) u=read(),v=read(),G[u].push_back(v),G[v].push_back(u);
	for(int i=0;i<=x;i++) A[i]=read();
	s=n*log2(n)/sqrt(m)+1;
	for(int i=1;i<=n;i++) fa1[i]=i;
	for(int i=1;i<=n;i++) rt[i]=new1(),ins(rt[i],a[i]);
	for(int i=n;i>=1;i--) {
		int j=i;
		tim=0;
		flag[i]=1;
		int t1;
		for(const auto &lxl:G[i]) {
			if(flag[lxl]) {
				t1=get(lxl,fa1);
				if(tr[rt[i]].s>tr[rt[t1]].s) swap(rt[i],rt[t1]);
				fa1[t1]=i;
				merge(rt[i],rt[t1],0);
			}
		}
		while(j>1) {
			j--;
			flag[j]=1;
			for(const auto &lxl:G[j]) {
				if(flag[lxl]) {
					t1=get(lxl,fa1);
					if(tr[rt[j]].s>tr[rt[t1]].s) swap(rt[j],rt[t1]);
					fa1[t1]=j;
					merge(rt[j],rt[t1],0);
				}
			}
			if(tim>s) break;
		}
		if(tim>s) j++;
		bls++;
		for(int k=j;k<=i;k++) idx[k]=bls;
		L[bls]=j,R[bls]=i;
		i=j;
	}
	for(int i=1;i<=n;i++) idx[i]=bls-idx[i]+1;
	for(int i=1;i<=bls;i++) 
		if(i<bls-i+1) swap(L[i],L[bls-i+1]),swap(R[i],R[bls-i+1]);
	for(int i=1;i<=m;i++) p[i].l=read(),p[i].r=read(),p[i].id=i;
	sort(p+1,p+m+1);
	for(int now=-1,z=1;z<=m;z++) {
		pl=p[z].l,pr=p[z].r;
		if(idx[pl]==idx[pr]) {
			cnt1=cnt2=top=ans=0;
			for(int i=pl;i<=pr;i++) {
				fa1[i]=i;
				rt[i]=new1(),ins(rt[i],a[i]),ans+=A[1];
				int t1;
				for(const auto &lxl:G[i]) 
					if(pl<=lxl&&lxl<=i) {
						t1=get(lxl,fa1);
						if(tr[rt[i]].s>tr[rt[t1]].s) 
							swap(rt[i],rt[t1]);
						fa1[t1]=i;
						ans-=A[tr[rt[i]].s],ans-=A[tr[rt[t1]].s];
						merge(rt[i],rt[t1],0);
						ans+=A[tr[rt[i]].s];
					}
			}
			Ans[p[z].id]=ans;
			continue;
		}
		if(now!=idx[pl]) {
			now=idx[pl];
			l=R[now],r=l-1;
			ans=cnt1=cnt2=top=0;
			memset(flag,0,sizeof(flag));
			for(int i=1;i<=n;i++) fa1[i]=i,rt[i]=new1(),ins(rt[i],a[i]);
		} 
		int t1;
		while(r<pr) {
			++r;
			flag[r]=1;
			fa1[r]=r;
			ans+=A[1];
			for(const auto &lxl:G[r]) 
				if(flag[lxl]) {
					t1=get(lxl,fa1);
					if(tr[rt[r]].s>tr[rt[t1]].s) swap(rt[r],rt[t1]);
					fa1[t1]=r;
					ans-=A[tr[rt[r]].s],ans-=A[tr[rt[t1]].s];
					merge(rt[r],rt[t1],0);
					ans+=A[tr[rt[r]].s];
				}
		}
		aans=ans;vec.clear();
		for(int i=l-1;i>=pl;i--) {
			fa2[i]=i,aans+=A[1];
			flag[i]=1;
			vec.push_back(i);
			for(const auto &lxl:G[i]) 
				if(flag[lxl]) {
					t1=get(lxl,fa1);
					if(fa2[t1]) fa2[get(t1,fa2)]=i;
					else fa2[t1]=i,vec.push_back(t1);
				}
		}
		for(const auto &lxl:vec) aans-=A[tr[rt[lxl]].s],rt2[lxl]=rt[lxl];
		for(const auto &lxl:vec) {
			t1=get(lxl,fa2);
			if(t1!=lxl) {
				tim++;
				if(tr[rt2[t1]].s>tr[rt2[lxl]].s) swap(rt2[t1],rt2[lxl]);
				canc[++ccnt]=(Canc){rt2[t1],rt2[lxl]};
				merge(rt2[t1],rt2[lxl],1);
			}
		}
		for(const auto &lxl:vec) {
			if(fa2[lxl]==lxl) aans+=A[tr[rt2[lxl]].s];
			fa2[lxl]=0;
		}
		Ans[p[z].id]=aans;
		while(ccnt) merge(canc[ccnt].x,canc[ccnt].y,1),ccnt--;
		for(int i=pl;i<l;i++) flag[i]=0;
	}
	for(int i=1;i<=m;i++) printf("%d\n",Ans[i]);
	return 0;
}