CF702E Analysis of Pathes in Functional Graph 题解

发布于 2020-08-18  690 次阅读


为什么这么裸的题是紫题。

题意

题目链接

注意权值最小值指的是这 $k$ 条边中权值最小的那条边的值就好,题意叙述的很清楚了。另外注意点号是从 $0$ 开始的。

解析

一看数据范围, $1 \le k \le 10^{10}$ ,很显然正常跑跑不了,既然要快速跑,而本题中又没有对边的权值进行改变,再给了每个点有且仅有一条出边,很容易就能想到倍增

但这道题的关键在于,怎样倍增才是最方便的。显然,如果先建图再倍增,非常麻烦且多次一举。对于倍增,我们只要知晓初值,就可能进行倍增操作了。而本题中很显然所给出的边的权值既是权值和的初值,又是权值最小值的初值,因此我们无须建图,再输入完数据后就可能直接进行倍增。

而查询时,我们只要像跑lca一样大块的优先查掉就可以了。

时间复杂度

倍增的预处理的时间复杂度是 $O(n\log k)$ ,每次查询操作的时间复杂度是 $O(\log k)$,会进行 $n$ 次操作,因此最终时间复杂度为 $O(n\log k)$ ,非常优良。

代码

#include<bits/stdc++.h>
#define int long long
#define N 100005
using namespace std;
int minn[N][36],f[N][36],son[N][36],n,k;
inline void solve(int u){//查询 
    int ans=0,Min=1e18;
    int K=k;
    for(int i=35;i>=0;i--){
        if((1ll<<i)<=K){
            ans+=f[u][i];
            Min=min(Min,minn[u][i]);
            u=son[u][i];
            K-=(1ll<<i);
        }
    }
    printf("%lld %lld\n",ans,Min);
}
signed main(){
    scanf("%lld%lld",&n,&k);
    for(int i=0;i<n;i++) scanf("%lld",&son[i][0]);
    for(int i=0;i<n;i++){scanf("%lld",&f[i][0]);minn[i][0]=f[i][0];}
    for(int j=1;j<=35;j++){//预处理 
        for(int i=0;i<n;i++){
            son[i][j]=son[son[i][j-1]][j-1];
            f[i][j]=f[i][j-1]+f[son[i][j-1]][j-1];
            minn[i][j]=min(minn[i][j-1],minn[son[i][j-1]][j-1]);
        }
    }
    for(int i=0;i<n;i++){
        solve(i);
    }
    return 0;
}

月流华 岁遗沙 万古吴钩出玉匣