部分点解法

\(X_i = i\) を満たす整数 \(i\) はただ一つに定まります。この \(i\) を \(r\) とします。与えられたグラフから \(r\to r\) の辺を取り除いたとき、グラフは頂点 \(r\) を根とする（各辺が根の方向へ向かう）有向木となります。

各頂点の答えへの寄与を

1. 頂点 \(r\) にたどりつくまで
2. 頂点 \(r\) にたどり着いた後

に分解して求めます。

後者については、深さごとの \(A_i\) の和の列を求め、累積和を取り、各項に \(B_r\) を掛ければ求まります。

前者は重心分解を用いて解きます。

重心を一つ取り \(g\) とします。\(g\) を根とする部分木内の頂点が、\(g\) へたどり着いた後の寄与を一気に計算します。これは「\(g\) を根としたときの深さごとの \(A_i\) の和の列」と「\(g\) の祖先の \(B_i\) の列」の畳み込みを行えば計算できます。ただし、すでに寄与を計算した頂点分を再度加算しないように注意してください。（通常の重心分解のように、すでに重心として用いた頂点を消すようにすればよいです。）

それぞれの列の長さは現在注目している木の大きさで抑えられるため、通常の重心分解と同様の計算量解析が回ります。したがって \(\mathrm{O}(N\log^2 N)\) で部分点を得られます。

満点解法

与えられるグラフはただ \(1\) つ有向サイクルを持ちます。サイクル上の頂点を任意に一つとり \(r\) とします。このグラフから \(r\to X_r\) の辺を取り除くと、グラフは頂点 \(r\) を根とする（各辺が根の方向へ向かう）有向木となります。

部分点解法と同様、各頂点の答えへの寄与を

1. 頂点 \(r\) にたどりつくまで
2. 頂点 \(r\) にたどり着いた後

に分解して求めます。

前者の求め方は部分点解法と同様です。後者は、深さごとの \(A_i\) の和の列と、\((B_r, B_{X_r}, B_{X_{X_r}}, \ldots)\) という列の畳み込みを行えば寄与が求まります。

したがって \(\mathrm{O}(N\log^2 N)\) で満点を得られます。