8820

dottle · 2022-10-31 11:12:27 · 题解

首先，我们稍微把题意转化一下：我们要寻找一条从 s 到 t 的路径，然后将其上的若干个点将点权计入答案，要求不存在连续 K 个不计入答案的点。

首先，考虑如何暴力地解决问题。我们可以设 (k,x) 表示走到 k 这个点，当前已经有 x 个点没有标记了。然后便可以建图：

若原图有边 k\to t，且 x+1<K：

在此图上跑最短路即可，单次复杂度 O(n\log n )。

接下来，考虑优化此过程。对于 s 到 t 路径上的点来说，他们可能不会计入答案，但是一定会被经过。我们可以据此倍增优化我们的算法。

考虑求出这样一个数组：

那么我们只需要手动分析 dis_{k,0,x,y} 的情况，经过讨论，有以下三种情况：

1. 走到 fa 后，将 fa 计入答案。
3. 预处理好 $dis$ 数组后，回答每次询问，我们先求出 $(lca,0\sim K-1)$ 到 $(s,0),(t,0)$ 的距离，假设我们从 $(s,0)$ 走到了 $(lca,x)$；从 $(t,0)$ 走到了 $(lca,y)$ ，那么：

• 若 x=y=0，则 lca 的点权多算了一次，需要减掉；
• 若 x=y=2，则还需要在 lca 附近的一个点中转一次，需要补上一个权值；
• 否则，直接把两段路径拼起来就可以。

时间复杂度 O(3^3n\log n)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200500,B=20,K=3;

int n,q,T;
int v[N],mn[N];
vector<int> e[N];

int f[B][N],dep[N];
int dis[B][N][K][K];

void gi(int&x,int y){x=min(x,y);}

void dfs(int k,int fa){

    dep[k]=dep[fa]+1;

    f[0][k]=fa;
    for(int i=1;i<B;i++)f[i][k]=f[i-1][f[i-1][k]];

    auto D=dis[0][k];
    if(T==1){
        D[0][0]=v[fa];
    }
    if(T==2){
        D[0][0]=D[1][0]=v[fa];
        D[0][1]=0;
    }
    if(T==3){
        D[0][0]=D[1][0]=D[2][0]=v[fa];
        D[0][1]=D[1][2]=0;
        D[2][2]=mn[k];
    }

    for(int i=1;i<B;i++)
        for(int x=0;x<3;x++)
            for(int y=0;y<3;y++)
                for(int z=0;z<3;z++)
                    gi(dis[i][k][x][z],dis[i-1][k][x][y]+dis[i-1][f[i-1][k]][y][z]);

    for(auto to:e[k])if(to!=fa)
        dfs(to,k);
}

int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=B-1;i>=0;i--)
        if(dep[f[i][x]]>=dep[y])
            x=f[i][x];
    if(x==y)return x;
    for(int i=B-1;i>=0;i--)
        if(f[i][x]!=f[i][y])
            x=f[i][x],y=f[i][y];
    return f[0][x];
}

vector<int> calc(int k,int l){
    vector<int> res(3,v[k]);
    for(int i=B-1;i>=0;i--){
        if(dep[f[i][k]]<dep[l])continue;
        vector<int> nw=res;
        fill(res.begin(),res.end(),1e18);
        for(int x=0;x<3;x++)
            for(int y=0;y<3;y++)
                gi(res[y],nw[x]+dis[i][k][x][y]);
        k=f[i][k];
    }
    return res;
}

int calcdis(int x,int y){
    int l=lca(x,y);
    auto F=calc(x,l),G=calc(y,l);
    int res=1e18;
    gi(res,F[0]+G[0]-v[l]);
    for(int i=0;i<T;i++)for(int j=0;j<T;j++){
        gi(res,F[i]+G[j]+(mn[l]*(i+j>T)));
    }
    return res;
}

main(){
    ios::sync_with_stdio(0);
    cin>>n>>q>>T;
    for(int i=1;i<=n;i++){
        cin>>v[i];
        mn[i]=v[i];
    }
    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
        mn[x]=min(mn[x],v[y]);
        mn[y]=min(mn[y],v[x]);
    }
    memset(dis,1,sizeof(dis));
    dfs(1,0);

    while(q--){
        int s,t;cin>>s>>t;
        cout<<calcdis(s,t)<<'\n';   
    }

}