记录编号	577510	评测结果	AAAAAAAAAAATTAAATTTAAATTT
题目名称	[CSP 2022S]数据传输	最终得分	68
用户昵称	00000	是否通过	未通过
代码语言	C++	运行时间	27.479 s
提交时间	2022-11-07 15:17:12	内存使用	0.00 MiB

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,t,k,v[300000],ans;
vector<ll> g[300000];
ll fa[300000],d[300000];//父亲，深度 
ll a[300000],b[300000],aa,bb,f[300000];
void dfs(ll x,ll y,ll z)//z:父亲 
{
	d[x]=y;fa[x]=z;
	for(ll q:g[x])
	{
		if(q!=z) dfs(q,y+1,x);
	}
}
void work()//k=2
{
		b[1]=b[1];
		b[2]=b[1]+b[2];
		for(int q=3;q<=bb;q++)
		{
			b[q]=b[q]+min(b[q-1],b[q-2]);
		}
}
void work3()//k=3
{
		f[1]=b[1];b[1]=v[b[1]];
		f[2]=b[2];b[2]=b[1]+v[b[2]];
		if(bb>=3)
		{
			f[3]=b[3];
			b[3]=min(b[1],b[2])+v[b[3]];
			for(int q=4;q<=bb;q++)
			{
				f[q]=b[q];
				if(q>=5)
				{
					ll c=0x3f3f3f3f;
					for(ll w:g[f[q-2]]) c=min(c,v[w]);
						 
					b[q-3]=min(b[q-3],c+b[q-4]);
				}
				b[q]=v[b[q]]+min({b[q-1],b[q-2],b[q-3]});
			}
		}
}
int main(){
	freopen("csp2022_transmit.in","r",stdin);
	freopen("csp2022_transmit.out","w",stdout);
cin>>n>>t>>k;
for(int q=1;q<=n;q++) cin>>v[q];
v[0]=0x3f3f3f3f;
for(int q=1;q<n;q++)
{
	ll x,y;
	cin>>x>>y;
	g[x].push_back(y);
	g[y].push_back(x);
}
dfs(1,1,0);
while(t--)
{
	aa=bb=0;
	ans=0;
	ll x,y;
	cin>>x>>y;
	if(d[x]>d[y]) swap(x,y);
	if(k==1)
	{
		while(d[x]!=d[y])
		{
			ans+=v[y];
			y=fa[y];
		}
		while(x!=y)
		{
			ans+=v[y];
			y=fa[y];
			ans+=v[x];
			x=fa[x];
		}
		ans+=v[x];
		cout<<ans<<endl;
	}
	if(k==2)
	{
		while(d[x]!=d[y]&&fa[y]!=x)
		{
			b[++bb]=v[y];
			y=fa[y];
		}
		if(fa[y]==x)
		{
			b[++bb]=v[y];b[++bb]=v[x];
			work();
			cout<<b[bb]<<endl;
			continue;
		}
		while(x!=y)
		{
			b[++bb]=v[y];y=fa[y];
			a[++aa]=v[x];x=fa[x];
		}
		b[++bb]=v[y];
		for(int q=aa;q>=1;q--) b[++bb]=a[q];
		work();
		cout<<b[bb]<<endl;
	}
	if(k==3)//去v 
	{
		while(d[x]!=d[y]&&fa[y]!=x)
		{
			b[++bb]=y;
			y=fa[y];
		}
		if(fa[y]==x)
		{
			b[++bb]=y;b[++bb]=x;
			work3();
			cout<<b[bb]<<endl;
			continue;
		}
		while(x!=y)
		{
			b[++bb]=y;y=fa[y];
			a[++aa]=x;x=fa[x];
		}
		b[++bb]=y;
		for(int q=aa;q>=1;q--) b[++bb]=a[q];
		work3();
		cout<<b[bb]<<endl;
	}
}
return 0;
}