今日はこれの解説を書きます．
問題概要
\(n\) 頂点 \(n\) 辺の有向グラフがあり，頂点 \(i\) からは \(f_i\) に辺が伸びています． すなわち，頂点 \(i\) の行き先はちょうど一つに定まります．
頂点 \(i\) から（\(f_i\) に）遷移するときのコストは \(w_i\) です． 各頂点 \(i\) について，「\(i\) から \(k\) 回の遷移を行うときに発生する（重複を含めて \(k\) 個の）コストの総和と最小値」をそれぞれ求めてください．
考察
頂点 \(i\) から \(1\) 回遷移したときのコストは（入力から）わかっています． ここで，\(w_i\) と \(w_{f_i}\) を見て，頂点 \(i\) から \(2\) 回遷移したときのコストも求めることができます． このとき，\(f_i\) と \(f_{f_i}\) も見て，頂点 \(i\) から \(2\) 回遷移したときの遷移先の頂点も求めておきます．
同様にして，\(2^i\) 回遷移したときのコストと遷移先の頂点から，\(2^{i+1}\) 回遷移したときのそれらを求めることが可能です．
各操作は \(O(n)\) で計算でき，この操作は \(O(\log k)\) 回行えば十分なので，全体の計算量は \(O(n\log k)\) です．
繰り返し二乗法の要領で，\(k\) の特定のビットを見ながら更新していき，全体の答えを求めることができます． 今いる頂点と，今までのコストから計算した値を持っておいて，その頂点から \(2^i\) 回遷移したときにどうなるかを考えて更新していけばよいです．
ところで，適当な型の総和も最小値もモノイド*1 なので，抽象化して作っておくと，一回の実装で済ませられて便利です．というか片方だけバグらせるみたいな事故を防げるのがうれしい．
実装
main() はこれだけ．
int main() {
size_t n;
uintmax_t k;
scanf("%zu %ju", &n, &k);
std::vector<size_t> f(n);
for (auto& fi: f) scanf("%zu", &fi);
std::vector<intmax_t> w(n);
for (auto& wi: w) scanf("%jd", &wi);
auto s = transition(f, w, add<intmax_t>(), k);
auto m = transition(f, w, min<intmax_t>(), k);
for (size_t i = 0; i < n; ++i)
printf("%jd %jd\n", s[i], m[i]);
}
add と min はこんな感じで作っておきます．
template <typename Tp>
struct add {
Tp const identity = 0;
Tp operator ()(Tp const& x, Tp const& y) const { return x + y; }
};
template <typename Tp>
struct min {
Tp const identity = std::numeric_limits<Tp>::max();
Tp operator ()(Tp const& x, Tp const& y) const { return std::min(x, y); }
};
これはえびちゃんのライブラリでありがちなんですが，単位元を表す Tp const identity と，適当な演算を行う Tp operator ()(Tp const&, Tp const&) const を持たせておきます．ここら辺はよしなに．
実際にダブリングを行う transition() はこんな感じ．
template <typename Tp, typename Fn>
std::vector<Tp> transition(std::vector<size_t> const& dst,
std::vector<Tp> const& value,
Fn f, uintmax_t k) {
size_t n = dst.size();
std::vector<Tp> res_v(n, f.identity);
std::vector<size_t> res_d(n);
std::iota(res_d.begin(), res_d.end(), 0);
std::vector<Tp> dbl_v = value;
std::vector<size_t> dbl_d = dst;
for (; k; k >>= 1) {
if (k & 1) {
std::vector<size_t> tmp_d = res_d;
for (size_t i = 0; i < n; ++i) {
res_v[i] = f(res_v[i], dbl_v[tmp_d[i]]);
res_d[i] = dbl_d[tmp_d[i]];
}
}
{
std::vector<Tp> tmp_v = dbl_v;
std::vector<size_t> tmp_d = dbl_d;
for (size_t i = 0; i < n; ++i) {
dbl_v[i] = f(dbl_v[i], tmp_v[tmp_d[i]]);
dbl_d[i] = tmp_d[tmp_d[i]];
}
}
}
return res_v;
}
繰り返し二乗法の要領です． えびちゃん的には繰り返し二乗法は当然非再帰で書くんですが，そうでない人はよしなに．
