文件详细信息

下载本文件

本文件的大小为 3132 字节。

//参考资料：https://www.cnblogs.com/sizeof127/p/16841791.html
#include<cstdio>
template<typename T>
void read(T&num){
	int ch=getchar();
	num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
}
template<typename T>
void write(T a){
	static int ch[30],cnt=0;
	if(a<0)putchar('-'),a=-a;
	if(a==0)putchar('0');
	while(a)ch[cnt++]=a%10|48,a/=10;
	while(cnt)putchar(ch[--cnt]);
}
template<typename T>
void chkmin(T&a,const T b){
	if(a>b)a=b;
}
typedef long long ll;
const int maxn=200005,maxlg2n=18;
const ll inf=0x3f3f3f3f3f3f3f3f;
struct Matrix{
	ll v[3][3];
	Matrix(ll val){
		for(int i=0;i<3;i++)
			for(int j=0;j<3;j++)
				v[i][j]=val;
	}
	ll*operator[](const int x){
		return v[x];
	}
	Matrix(){}
}I(inf),up[maxn][maxlg2n],dn[maxn][maxlg2n];
Matrix operator*(const Matrix a,const Matrix b){
	Matrix ans(inf);
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			for(int k=0;k<3;k++)
				chkmin(ans[i][j],a.v[i][k]+b.v[k][j]);
	return ans;
}
int n,q,k;
int head[maxn],total;
struct Edge{
	int to,next;
}e[maxn<<1];
void add(int u,int v){
	e[++total]=Edge{v,head[u]};
	head[u]=total;
}
ll a[maxn][2];
int lg2[maxn],dep[maxn],lim,fa[maxn][maxlg2n];
Matrix init(int id){
	Matrix ans(inf);
	if(k==1)ans[0][0]=a[id][0];
	else if(k==2){
		ans[0][0]=a[id][0],ans[0][1]=0;
		ans[1][0]=a[id][0];
	}else{
		ans[0][0]=a[id][0],ans[0][1]=0;
		ans[1][0]=a[id][0],ans[1][1]=a[id][1],ans[1][2]=0;
		ans[2][0]=a[id][0];
	}
	return ans;
}
void dfs(int u,int from){
	dep[u]=dep[from]+1;
	fa[u][0]=from;
	lim=lg2[dep[u]];
	for(int i=1;i<=lim;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to;
		if(v==from)continue;
		chkmin(a[v][1],a[u][0]);
		chkmin(a[u][1],a[v][0]);
		dfs(v,u);
	}
	up[u][0]=dn[u][0]=init(u);
}
int lca(int u,int v){
	if(dep[u]<dep[v])u^=v^=u^=v;
	while(dep[u]>dep[v])u=fa[u][lg2[dep[u]-dep[v]]];
	if(u==v)return u;
	for(int i=lg2[dep[u]];i>=0;i--)
		if(fa[u][i]!=fa[v][i])
			u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}
int nxt(int u,int anc){
	for(int i=lg2[dep[u]];i>=0;i--)
		if(dep[fa[u][i]]>dep[anc])
			u=fa[u][i];
	return u;
}
Matrix get(int id){
	Matrix ans(inf);
	ans[0][0]=a[id][0];
	return ans;
}
Matrix jump(int u,int anc,int type){
	if(dep[u]<=dep[anc])return I;
	Matrix ans=I;
	for(int i=lg2[dep[u]];i>=0;i--)
		if(dep[fa[u][i]]>=dep[anc]){
			ans=(type==0)?ans*up[u][i]:dn[u][i]*ans;
			u=fa[u][i];
		}
	return ans;
}
Matrix query(int S,int T){
	if(S==T||fa[S][0]==T||fa[T][0]==S)return I;
	int U=lca(S,T);
	Matrix mid=(U!=S&&U!=T)?init(U):I;
	return jump(fa[S][0],U,0)*mid*jump(fa[T][0],U,1);
}
int main(){
	I[0][0]=I[1][1]=I[2][2]=0;
	read(n),read(q),read(k);
	for(int i=2;i<=n;i++)lg2[i]=lg2[i-1]+((i&(i-1))==0);
	for(int i=1;i<=n;i++)read(a[i][0]),a[i][1]=inf;
	for(int i=1,u,v;i<n;i++){
		read(u),read(v);
		add(u,v),add(v,u);
	}
	dfs(1,0);
	for(int i=1;i<maxlg2n;i++)
		for(int u=1;u<=n;u++){
			up[u][i]=up[u][i-1]*up[fa[u][i-1]][i-1];
			dn[u][i]=dn[fa[u][i-1]][i-1]*dn[u][i-1];
		}
	for(int i=1,u,v;i<=q;i++){
		read(u),read(v);
		Matrix ans=get(u)*query(u,v)*init(v);
		write(ans[0][0]),putchar('\n');
	}
	return 0;
}