题意

给定一个有向图，每条边有一个权值。对于每个顶点 $u$，需要求出从 $u$ 出发，经过恰好 $k$ 条边（路径长度为 $k$）的路径信息，包括：

• 终点顶点编号
• 路径上所有边的权值之和
• 路径上所有边权的最小值

思路

本题可以利用二进制快速幂的思想解决。

定义结构体 $fr[u]$ 表示从顶点 $u$ 出发、长度为 $r$ 的路径信息，包含：

• $fr[u].to$：从 $u$ 出发长度为 $r$ 的路径的终点顶点编号
• $fr[u].len$：从 $u$ 出发长度为 $r$ 的路径上所有边的权值之和
• $fr[u].min$：从 $u$ 出发长度为 $r$ 的路径上所有边权的最小值

如果已知所有顶点在长度 $r_1$ 和 $r_2$ 下的信息，则可以合并得到长度 $r_1 + r_2$ 的信息：

• $fr_1 + r_2[u].to = fr_2[fr_1[u].to].to$
  即先从 $u$ 走 $r_1$ 步到达 $fr_1[u].to$，再从这个顶点走 $r_2$ 步。
• $fr_1 + r_2[u].len = fr_1[u].len + fr_2[fr_1[u].to].len$
• $fr_1 + r_2[u].min = \min(fr_1[u].min, fr_2[fr_1[u].to].min)$

因此，将两个长度为 $r_1$ 和 $r_2$ 的数组“合并”得到长度为 $r_1 + r_2$ 的数组，这一操作可以看作“乘法”。那么，要求长度为 $k$ 的数组 $f_k$，只需将长度为 $1$ 的数组 $f_1$ 进行 $k$ 次幂运算（即重复合并），利用二进制快速幂即可高效求解。

此外，本题也可以用“二进制拆分”的方法解决，但本质上与上述方法相同。

算法步骤

1. 初始化 $f_1$ 数组：对于每个顶点 $u$，根据其出边信息，得到长度为 $1$ 的路径信息（终点、长度、最小值）。
2. 将 $k$ 表示为二进制形式。
3. 使用快速幂思想：
   • 设结果数组 $res$ 初始为单位数组（长度为 $0$ 的路径信息，即 $res[u].to = u$，$res[u].len = 0$，$res[u].min = +\infty$）。
   • 设当前幂次数组 $cur = f_1$。
   • 遍历 $k$ 的二进制位，若当前位为 $1$，则将 $res$ 与 $cur$ 合并（即 $res = res \times cur$）。
   • 每次将 $cur$ 自乘（即 $cur = cur \times cur$），对应长度翻倍。
4. 最终 $res$ 即为长度为 $k$ 的路径信息数组。

复杂度分析

• 时间复杂度：$O(n \log k)$，其中 $n$ 为顶点数，$\log k$ 为快速幂的迭代次数。
• 空间复杂度：$O(n)$，用于存储每个顶点的路径信息。

代码说明

• 定义结构体 Node，包含 to、len、min 三个字段。
• 实现合并函数 merge(Node a, Node b)，返回合并后的新节点。
• 实现快速幂函数 power(Node f[], int k)，返回长度为 $k$ 的路径信息数组。
• 主函数中读入图数据，初始化 $f_1$，然后调用快速幂得到结果并输出。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
using namespace std;
const int num=1e5+5;
typedef long long ll;
struct Node{
	// data表示祖先，Min表示路径最小值，N表示路径和 
	ll data,Min,N;
};
ll head[num],ver[2*num],edge[num*2],Next[2*num],tot=0;
void add(ll x,ll y,ll z){
	ver[++tot]=y;edge[tot]=z;Next[tot]=head[x];head[x]=tot;
}Node fat[num][45];ll t;
void bfs(ll h){
	queue<ll>q;q.push(h);
	while(!q.empty()){
		ll x=q.front();q.pop();
		if(fat[x][0].data!=-1)continue;
		for(ll i=head[x];i;i=Next[i]){
			ll y=ver[i];
			fat[x][0].data=y;fat[x][0].Min=fat[x][0].N=edge[i];
			q.push(y);
		}
	}
}
int main(){
	ll n,m,i,j,k;scanf("%lld%lld",&n,&m);
	ll a[num];t=(ll)(log(m)/log(2))+1;
	for(i=0;i<n;i++){
		scanf("%lld",&a[i]);
	}for(i=0;i<n;i++){
		scanf("%lld",&j);add(i,a[i],j);
	}for(i=0;i<n;i++){
		fat[i][0].data=-1;
	}for(i=0;i<n;i++){
		if(fat[i][0].data==-1){
			bfs(i);
		}
	}//更新fat[][]
    for(j=1;j<=t;j++){
		for(i=0;i<n;i++){
			fat[i][j].data=fat[fat[i][j-1].data][j-1].data;
			fat[i][j].Min=min(fat[fat[i][j-1].data][j-1].Min,fat[i][j-1].Min);
			fat[i][j].N=fat[i][j-1].N+fat[fat[i][j-1].data][j-1].N;
		}
	}for(i=0;i<n;i++){
		ll temp=m,hh=i,ans=-1,h=0;
		for(j=t;j>=0;j--){
			if(pow(2,j)<=temp){
				temp-=pow(2,j);h+=fat[hh][j].N;
				if(ans!=-1)
				ans=min(ans,fat[hh][j].Min);
				else
				ans=fat[hh][j].Min;
				hh=fat[hh][j].data;
			}
		}printf("%lld %lld\n",h,ans);
	}
}