求hack样例

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

int fa[600000][26];
vector<int> bian[600000+10];
vector<int> child[600000+10];
int dep[600000];
long long zhi[600000];
vector<int> dp;
vector<long long> num;
vector<long long> dpf;
stack<int> t;
long long sumzhi[600000];
long long f[600000];
int n,m,s;



long long pushin(int x,int l)
{
	if(x==l)return 0;
    long long ans=0;
    while(x!=l)
    {
        ans+=zhi[x];
        x=fa[x][0];
    }
    return ans;
}

void pushin1(int x,int l)
{
    long long ans=0;
    if(x==l)return;
    while(x!=l)
    {
        dp.push_back(x);
        x=fa[x][0];
    }
}

void pushin2(int x,int l)
{
	if(x==l)return ;
    long long ans=0;
    while(x!=l)
    {
        t.push(x);
        x=fa[x][0];
    }
    while(!t.empty())
    {
    	dp.push_back(t.top());
    	t.pop();
	}
}

long long godp()
{
	if(dp.size()<s+2)
	{
		long long ans=zhi[dp[0]]+zhi[dp[dp.size()-1]];
		//cout<<dp[0]<<' '<<dp[dp.size()-1]<<' '<<zhi[dp[0]]<<' '<<zhi[dp[dp.size()-1]]<<endl;
		num.clear();
		dp.clear();
		return ans;
	}
	//for(auto v:dp)cout<<v<<' ';cout<<endl;
	num.push_back(zhi[dp[0]]);
	num.push_back(zhi[dp[1]]+zhi[dp[0]]);
	for(int i=2;i<dp.size();i++)num.push_back(min(num[i-1],num[i-2])+zhi[dp[i]]);
	long long ans=num[num.size()-1];
	num.clear();
	dp.clear();
	return ans;
}

long long godp3()
{	
	if(dp.size()<s+2)
	{
		long long ans=zhi[dp[0]]+zhi[dp[dp.size()-1]];
		//cout<<dp[0]<<' '<<dp[dp.size()-1]<<' '<<zhi[dp[0]]<<' '<<zhi[dp[dp.size()-1]]<<endl;

		num.clear();
		dp.clear();
		dpf.clear();
		return ans;
	}
	//for(auto v:dp)cout<<v<<' ';cout<<endl;
	//for(auto v:dp)cout<<zhi[v]<<' ';cout<<endl;
	//for(auto v:dp)cout<<f[v]<<' ';cout<<endl;
	num.push_back(zhi[dp[0]]);
	num.push_back(zhi[dp[1]]+zhi[dp[0]]);
	num.push_back(zhi[dp[2]]+zhi[dp[0]]);
	dpf.push_back(zhi[dp[0]]+f[dp[0]]);
	dpf.push_back(zhi[dp[0]]+f[dp[1]]);
	dpf.push_back(zhi[dp[0]]+f[dp[2]]);
	for(int i=2;i<dp.size();i++)
		num.push_back(min({num[i-1],num[i-2],num[i-3],dpf[i-1],dpf[i-2]})+zhi[dp[i]]),
		dpf.push_back(min({num[i-1],num[i-2],dpf[i-1]})+f[dp[i]]);
	long long ans=num[num.size()-1];
	num.clear();
	dp.clear();
	dpf.clear();
	return ans;
}

void Build(int f,int s)
{//cout<<f<<' '<<s<<endl; 
    for(auto v:bian[s])
    {
        if(v!=f)child[s].push_back(v),Build(s,v);
    }
}

void init(int f,int s)
{
    fa[s][0]=f;
    for(int i=1;i<25;i++)fa[s][i]=fa[fa[s][i-1]][i-1];
    dep[s]=dep[f]+1;
    sumzhi[s]=sumzhi[f]+zhi[s];
    for(auto v:child[s])
    {
        init(s,v);
    }
}

void oneclimb(int & x,int & y)
{
    if(dep[x]>dep[y])swap(x,y);
    if(dep[x]==dep[y])return;
    for(int i=24;i>=0;i--)
    {
        if(dep[fa[y][i]]<dep[x])continue;
        y=fa[y][i];
        if(dep[y]==dep[x])return;
    }
}

int twoclimb(int x,int y)
{
    if(x==y)return x;
    for(int i=24;i>=0;i--)
    {
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    }
    return fa[x][0];
}

int lca(int x,int y)
{
    oneclimb(x,y);
   // cout<<x<<' '<<y<<'\n'; 
    return twoclimb(x,y);
}

int main()
{//freopen("transmit4.in","r",stdin);
// freopen("transmit.out","w",stdout);
ios::sync_with_stdio(0);
    cin>>n>>m>>s;int x,y;
    for(int i=1;i<=n;i++)cin>>zhi[i];
    for(int i=1;i<n;i++)
    {
        cin>>x>>y;
		bian[x].push_back(y);
		bian[y].push_back(x);
    }
    /*for(int i=1;i<=n;i++)
    {
        cout<<i<<':';
        for(auto v:bian[i])cout<<v<<' ';
        cout<<endl;
    }*/ 
	Build(0,s);
    
    for(int i=0;i<25;i++)fa[0][i]=0;
    init(0,s);
    if(s==3)
    	for(int i=1;i<=n;i++)
    	{
    		f[i]=zhi[bian[i][0]];
    		for(auto v:bian[i])
    			f[i]=min(f[i],zhi[v]);
		}
    while(m--)
    {
        int x,y; 
        cin>>x>>y;
        int l=lca(x,y);
       // cout<<endl;
        //cout<<l<<endl; 
        if(s==1)cout<<sumzhi[x]+sumzhi[y]-2*sumzhi[l]+zhi[l]<<endl;
        else {
        pushin1(x,l);
        dp.push_back(l);
        pushin2(y,l);
        
        cout<<(s==2?godp():godp3())<<endl;}
    }
    return 0;
}