题解：P9245 [蓝桥杯 2023 省 B] 景区导游

第一次写题解,不太会写QwQ,看了下和别的题解思路差不多

题意：

在一棵N个节点的树中,求若干有序到达节点按需删除节点的总代价

解题思路：

采用链式前向星存图,然后求出req数组的总代价sum,求出每次修改改变的代价即可。

先分析开头和结尾的简单情况(dis的下标指的是req数组的序号),如果第一个点跳过,sum要减去

dis_{12}

的代价,如果最后一个点要跳去,sum要减去

dis_{(k-1)k}

的代价。然后分析中间的情况,连续的abc三个点,跳开b点,

sum

dis_{ab}

dis_{bc}

dis_{ac}

的代价。至此我们只需要求这些点的距离即可,a到b的路径长度等于头节点到a的距离+头节点到b的距离-头节点到a和b最低公共祖先c距离*2,然后就用倍增法求lca就可以了

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e5+10;
const int MAXM = MAXN<<1;
const int LIMIT = 21;
int head[MAXN],nex[MAXM],to[MAXM],weight[MAXM];
int deep[MAXN],dis[MAXN];
int power;
int stjump[MAXN][LIMIT];
int req[MAXN];
int cnt=1;
int LOG2(int n){
    int ans=0;
    while((1<<ans)<=(n>>1)){
        ans++;
    }
    return ans;
}
void build(int n){
    fill(head+1,head+1+n,0);
    cnt=1;
    power = LOG2(n);
}
void addEdge(int u,int v,int w){
    nex[cnt]=head[u];
    to[cnt]=v;
    weight[cnt]=w;
    head[u]=cnt++;
}
void dfs(int u,int f,int w){
    dis[u]=w;
    if(f==0){
        deep[u] = 1;
        stjump[u][0]=u;
    }else{
        deep[u]=deep[f]+1;
        stjump[u][0]=f;
    }
    for(int p=1;p<=power;p++){
        stjump[u][p]=stjump[stjump[u][p-1]][p-1];
    }
    for(int i=head[u];i;i=nex[i]){
        if(to[i]!=f){
            dfs(to[i],u,weight[i]+w);
        }
    }
}
int lca(int a,int b){
    if(deep[a]<deep[b]) swap(a,b);
    for(int p=power;p>=0;p--){
        if(deep[stjump[a][p]]>=deep[b]){
            a = stjump[a][p];
        }
    }
    if(a==b) return a;
    for(int p=power;p>=0;p--){
        if(stjump[a][p]!=stjump[b][p]){
            a = stjump[a][p];
            b = stjump[b][p];
        }
    }
    return stjump[a][0];
}
int cal(int x,int y){
    return dis[x]+dis[y]-2*dis[lca(x,y)];
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,k;
    cin>>n>>k;
    build(n);
    for(int i=1;i<=n-1;i++){
        int u,v,w;
        cin>>u>>v>>w;
        addEdge(u,v,w);
        addEdge(v,u,w);
    }
    dfs(1,0,0);
    for(int i=1;i<=k;i++){
        cin>>req[i];
    }
    int sum=0;
    for(int i=1;i<k;i++){
        sum+=cal(req[i],req[i+1]);
    }
    for(int i=1;i<=k;i++){
        if(i==1){
            cout<<sum-cal(req[i],req[i+1])<<" ";
        }else if(i==k){
            cout<<sum-cal(req[i-1],req[i])<<" ";
        }else{
            cout<<sum-cal(req[i-1],req[i])-cal(req[i],req[i+1])+cal(req[i-1],req[i+1])<<" ";
        }
    }
    return 0;
}

题解：P9245 [蓝桥杯 2023 省 B] 景区导游

文章操作

题意：

解题思路：

相关推荐

评论

题解：P9245 [蓝桥杯 2023 省 B] 景区导游