为什么这么裸的题是紫题。
题意
注意权值最小值指的是这 $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;
}