S组T4正解

#include <bits/stdc++.h>
using namespace std;
int n,q,k;
const int N=1e4+5,M=4e5+5;
int a[N];
int u,v;
int head[N],ecnt;
struct edge{
    int v,nxt;
}e[M];
void add(int u,int v){
    e[ecnt].v=v;
    e[ecnt].nxt=head[u];
    head[u]=ecnt++;
}
int dep[N],fa[N],ch[N],siz[N],ind[N],top[N];
void dfs(int u,int f,int d){
    int max_ch=0;
    dep[u]=d;
    fa[u]=f;
    siz[u]=1;
    for(int i=head[u];i+1;i=e[i].nxt){
        int v=e[i].v;
        if(v==fa[u]) continue;
        dfs(v,u,d+1);
        siz[u]+=siz[v];
        if(siz[v]>max_ch){
            max_ch=siz[v];
            ch[u]=v;
        }
    }
}
int windex;
void dfs2(int u,int tp){
    ind[u]=++windex;
    top[u]=tp;
    if(ch[u]==0) return ;
    //cout<<u<<' '<<ch[u]<<endl;
    dfs2(ch[u],tp);
    for(int i=head[u];i+1;i=e[i].nxt){
        int v=e[i].v;
        if(v==fa[u]||v==ch[u]) continue;
        dfs2(v,v);
    }
}
int f[N][N];
void dp(int u){
    f[u][u]=a[u];
    for(int i=fa[u],q=1;i+1&&q<=k+1;i=fa[i],q++){
        for(int j=i;j+1;j=fa[j]){
            f[j][u]=min(f[j][u],f[j][i]+a[u]);
            //cout<<j<<' '<<u<<' '<<f[j][u]<<endl;
        }
    }
    for(int i=head[u];i+1;i=e[i].nxt){
        int v=e[i].v;
        if(v!=fa[u]) dp(v);
    }
}
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]];
    }
    if(dep[x]<dep[y]) return x;
    return y;
}
int main(){
    freopen("transmit.in","r",stdin);
    freopen("transmit.out","w",stdout);
    cin>>n>>q>>k;
    memset(head,-1,sizeof(head));
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n-1;i++){
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    dfs(1,-1,1);
    dfs2(1,1);
    dp(1);
    int x,y;
    /*cout<<lca(4,7)<<endl;
    cout<<f[1][5]<<endl;*/
    while(q--){
        cin>>x>>y;
        cout<<f[lca(x,y)][x]+f[lca(x,y)][y]-a[lca(x,y)]<<endl;
    }
    return 0;
}