我无语了 早知道数据点分治按n分了呀服啦

不是路径点权差分吗 哪写错了啊/ll

#include <bits/stdc++.h>
//#include <bits/extc++.h>
using namespace std;
//using namespace __gnu_pbds;

#define ll long long
#define int ll
#define pii pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define pb emplace_back
const int N=2e5+7;
struct edge
{
	int to,nxt;
}e[N<<1];
int h[N],etot;
inline void eadd(int x,int y)
{
	e[++etot].to=y;
	e[etot].nxt=h[x];
	h[x]=etot;
}
#define FOR(x) for(int i=h[x],y;y=e[i].to,i;i=e[i].nxt)
int siz[N],son[N],top[N],fa[N],dep[N];
int v[N],w[N];
void dfs1(int x)
{
	siz[x]=1;
	int mx=0;
	FOR(x)if(y!=fa[x])
	{
		dep[y]=dep[x]+1;
		fa[y]=x,w[y]=w[x]+v[y];
		dfs1(y);
		siz[x]+=siz[y];
		if(siz[y]>mx)mx=siz[y],son[x]=y;
	}
}
void dfs2(int x,int topn)
{
	top[x]=topn;
	if(!son[x])return;
	dfs2(son[x],topn);
	FOR(x)if(y!=fa[x]&&y!=son[x])dfs2(y,y);
}
inline int lca(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		x=fa[top[x]];
	}
	return dep[x]<dep[y]?x:y;
}
inline int W(int x,int y)
{
	int r=lca(x,y);
	return w[x]+w[y]-w[r]-w[fa[r]];
}
inline int dist(int x,int y)
{
	int r=lca(x,y);
	return dep[x]+dep[y]-2*dep[r];
}
int dis[2003];
bool vis[2003];
inline int dij(int s,int t)
{
	memset(vis,0,sizeof(vis));
	memset(dis,0x1f,sizeof(dis));
	priority_queue<pii>q;
	dis[s]=v[s];
	q.push(mk(0,s));
	while(!q.empty())
	{
		int x=q.top().se;
		q.pop();
		if(x==t)return dis[t];
		if(vis[x])continue;
		vis[x]=1;
		FOR(x)
		{
			if(dis[y]>dis[x]+v[y])
			{
				dis[y]=dis[x]+v[y];
				q.push(mk(-dis[y],y));
			}
		}
	}
	return dis[t];
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	int n,q,k;
	cin>>n>>q>>k;
	for(int i=1;i<=n;i++)cin>>v[i];
	for(int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		eadd(x,y),eadd(y,x);
	}
	dfs1(1),dfs2(1,1);
	if(k==1)
	{
		while(q--)
		{
			int x,y;
			cin>>x>>y;
			cout<<W(x,y)<<"\n";
		}
		return 0;
	}
	else
	{
		for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
		{
			if(fa[i]!=j&&fa[j]!=i&&dist(i,j)<=k)eadd(i,j),eadd(j,i);
		}
		while(q--)
		{
			int x,y;
			cin>>x>>y;
			cout<<dij(x,y)<<"\n";
		}
	}
	return 0;
}