rt

感觉每个数组都有用 测试是在 dfs 就时就炸了

#include<bits/stdc++.h>
#define N 200005
#define ll long long
using namespace std;
const ll inf = 1e17;
struct matrix {
	int n,m;
	ll r[4][4];
}c,f[N][19],g[N][19],bas[N],st,cl,t;
matrix operator *(matrix a,matrix b)
{
	c.n=a.n,c.m=b.m;
	for(int i=1;i<=c.n;i++)
		for(int j=1;j<=c.m;j++)	
			c.r[i][j]=inf;
	for(int i=1;i<=c.n;i++)
		for(int k=1;k<=a.m;k++)
			for(int j=1;j<=c.m;j++)
				c.r[i][j]=min(c.r[i][j],a.r[i][k]+b.r[k][j]);
	return c;
}
int n,m,k;
struct edge{
	int to,next;
}e[N*2];
int head[N],tot=1;
void add(int u,int v)
{
	e[tot]=(edge){v,head[u]};
	head[u]=tot++;
}
int fa[N][19],dep[N];
ll v[N];
void build()
{
	st.n=1,st.m=k;
	st.r[1][k]=0;
	for(int i=1;i<k;i++) st.r[1][i]=inf;
	cl.n=cl.m=k;
	for(int i=1;i<=k;i++)
		for(int j=1;j<=k;j++)
			if(i==j) cl.r[i][j]=0;
			else cl.r[i][j]=inf;
	for(int i=1;i<=n;i++)
	{
		bas[i].n=bas[i].m=k;
		if(k==1)
			bas[i].r[1][1]=v[i];
		if(k==2)
		{
			bas[i].r[1][1]=v[i],bas[i].r[1][2]=0;
			bas[i].r[2][1]=v[i],bas[i].r[2][2]=inf;
		}
		if(k==3)
		{
			ll minn=inf;
			for(int j=head[i];j;j=e[j].next) minn=min(minn,v[e[j].to]);
			bas[i].r[1][1]=v[i],bas[i].r[1][2]=0,bas[i].r[1][3]=inf,
			bas[i].r[2][1]=v[i],bas[i].r[2][2]=minn,bas[i].r[2][3]=0,
			bas[i].r[3][1]=v[i],bas[i].r[3][2]=inf,bas[i].r[3][3]=inf;
		}
	}
}
void dfs(int now,int fath)
{
	dep[now]=dep[fath]+1;
	fa[now][0]=fath;
	g[now][0]=f[now][0]=bas[now];
	for(int i=1;fa[now][i-1];i++)
	{
		fa[now][i]=fa[fa[now][i-1]][i-1];
		f[now][i]=f[now][i-1]*f[fa[now][i-1]][i-1];
		g[now][i]=g[fa[now][i-1]][i-1]*g[now][i-1];
	}
	for(int i=head[now];i;i=e[i].next)
	{
		int son=e[i].to;
		if(son==fath) continue;
		dfs(son,now);
	}
}
int Lca(int u,int v)
{
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=18;i>=0;i--)
		if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
	if(u==v) return u;
	for(int i=18;i>=0;i--)
		if(fa[u][i]^fa[v][i]) u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}
matrix s1,s2,lv;
ll upd(int x)
{
	return v[x];
}
ll solve(int u,int v)
{
	int lca=Lca(u,v);
	lv=bas[lca];
	if(k==3) lv.r[2][2]=min(lv.r[2][2],upd(fa[lca][0]));
	s1=st,s2=cl;
	for(int i=18;i>=0;i--)
		if(dep[fa[u][i]]>=dep[lca]) 
			s1=s1*f[u][i],u=fa[u][i];
	for(int i=18;i>=0;i--)
		if(dep[fa[v][i]]>=dep[lca]) 
			s2=g[v][i]*s2,v=fa[v][i];
	return (s1*lv*s2).r[1][1];
}
int main()
{
//	freopen("ex.in","r",stdin);
	scanf("%d%d%d",&n,&m,&k);
	v[0]=inf;
	for(int i=1;i<=n;i++)
		scanf("%lld",&v[i]);
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	build();
	dfs(1,0);
	while(m--)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		printf("%lld\n",solve(u,v));
	}
	return 0;
}