问题理解

我们有 $N$ 个点，每个点有一条出边 $i \to A_i$。
这构成一个基环内向树森林（每个连通分量是一个环，环上每个点可能挂着一棵树，树边指向环）。

初始从 $1$ 出发，走 $K$ 步（$K$ 极大，$N \le 10^5, K \le 10^{18}$），到达点 $p_0$。这是原图的 $K$ 步终点。

允许修改一条边：选择 $a,b$，把 $a$ 的出边改成 $b$。
修改后，重新从 $1$ 出发走 $K$ 步，要求到达 $i$。
我们要对每个 $i$ 计数这样的 $(a,b)$ 对数。

---

初步分析

在固定图中从 $1$ 出发走 $K$ 步，由于每个点出度为 $1$，路径唯一，且最终会进入一个环并循环。

设原图中从 $1$ 出发走无穷步，会进入一个环 $C$，环长 $L$，进入环前的链长度为 $d_{\text{enter}}$（$d_{\text{enter}}$ 是进入环前经过的节点数，从 $1$ 到环的第一个点的步数）。那么 $K$ 步后所在的位置可分类讨论：

1. 如果 $K < d_{\text{enter}}$，则还在入环链上。
2. 否则，到达环上的位置为从环入口开始走 $r = (K - d_{\text{enter}}) \bmod L$ 步所在的环上节点（环上编号从入口为 0 开始）。

对于原问题，我们首先要找出 $p_0$（原图 $K$ 步终点）。

---

修改的影响

情况分类

修改 $(a,b)$ 可能：

• 不影响 $K$ 步路径：无论如何改，$K$ 步依然到达原来的 $p_0$。这包括很多对 $(a,b)$。
• 改变路径，使得 $K$ 步到达不同的点 $i$。

我们要对每个 $i$ 计数 $(a,b)$。

---

关键观察

因为 $K \ge N$，所以在原图中，$K$ 步后一定在某个环上（因为链长度至多 $N-1$）。

记原图从 $1$ 出发的无穷路径是： $ 1 \to x_1 \to x_2 \to \dots \to x_{d_{\text{enter}}} \to c_0 \to c_1 \to \dots \to c_{L-1} \to c_0\dots $ 其中 $c_0$ 是环入口，$c_i$ 是环上第 $i$ 个点（$c_L = c_0$）。

---

原终点计算

设 $K \ge d_{\text{enter}}$，那么 $ \text{原终点 } p_0 = c_{r},\quad r = (K - d_{\text{enter}}) \bmod L。 $

---

修改后的影响分类

1. 修改不涉及路径上的点

如果 $a$ 不在原路径 $1 \to p_0$ 的 $K$ 步节点序列中，并且 $a$ 不在 $p_0$ 的“前驱树”中（这里的前驱指原图的反向边能到 $a$ 且在 $K$ 步路径中），那么改 $a$ 的出边不影响路径，终点还是 $p_0$。这对计数到 $p_0$ 有帮助。

---

2. 修改涉及路径上的点

这是关键部分。
把原路径 $K$ 步节点列出来： $v_0=1, v_1, v_2, \dots, v_K$ 其实我们不需要显式计算 $v_K$，因为 $K$ 很大，会进入循环部分。

更有效的方法：考虑修改 $a$ 的出边到 $b$。

子情况 2.1：$a$ 在环外树部分（不在环上）

如果 $a$ 在环 $C$ 外，那么原路径可能会因为改边而提前进入其他环或原环的不同入口，需要仔细分析，但有一个系统的方法：

用倍增法或周期分析法：

• 原路径上每个节点 $v_t$ 的 $K-t$ 步后会到 $p_0$。
• 如果我们在 $a$ 处改到 $b$，那么从 1 到 $a$ 的原路径不变，到 $a$ 后走一步到 $b$，然后从 $b$ 走 $K-\text{dist}(1,a)-1$ 步到达最终点。

所以关键是计算从 $b$ 出发走 $M = K - \text{dist}(1,a) - 1$ 步会到哪。
$M$ 可能很大，我们需要知道 $b$ 所在的连通分量的环长等信息。

---

3. 环上修改特别分析

若 $a$ 在环 $C$ 上，那么原路径可能在绕环若干次后到达 $p_0$。改 $a$ 到 $b$ 会打破环，可能：

• 使路径走到另一个环。
• 或进入同一个环的不同位置，最终 $K$ 步终点改变。

---

统一框架

定义：

• $\text{distFrom1}(u)$：原图中从 $1$ 到 $u$ 的步数（如果不可达则为 $\infty$）。
• $\text{cycleLen}(u)$：$u$ 所在环的长度（如果 $u$ 在树上，则指从 $u$ 出发走无穷步进入的环的长度）。
• $\text{enterCyclePos}(u)$：从 $u$ 出发走无穷步首次进入环时的环上节点（环上编号）。

但我们不能直接显式计算 $K$ 步后的位置，必须用模运算。

---

更简洁的方法（官方解法思路）：

步骤 1：找出所有环

原图每个连通分量是一个基环树。找出所有环长 $L_c$ 和环上节点。

步骤 2：原终点 $p_0$

计算 $p_0$。

步骤 3：分类计数

令 $t = K$ 非常大，所以对于大多数 $a$，$K - \text{dist}(1,a) - 1$ 仍然很大（$\ge N$），所以从 $b$ 出发的剩余步数足够进入环并绕圈。

因此最终位置仅取决于：

1. $b$ 所在的环 $C'$ 的环长 $L'$，
2. 从 $b$ 出发走 $M$ 步后，在环 $C'$ 上的偏移量 $(M - \text{distToCycle}(b)) \bmod L'$。

其中 $\text{distToCycle}(b)$ 是 $b$ 到它所在环的入口距离。

---

数学简化

设我们选择 $a$，设 $D = \text{dist}(1,a)$。
若 $D > K$，那么 $a$ 不在 $K$ 步路径上，改 $a$ 不影响前 $K$ 步（因为走不到 $a$），所以终点还是 $p_0$。但 $K \ge N$，而 $D$ 最大 $N-1$，所以不可能 $D > K$（因为 $K \ge N$）。
所以任何 $a$ 都可能在 $K$ 步路径上？不一定，如果 $a$ 不在 1 能到达的点中，则 $D=\infty$，那么改 $a$ 不影响 1 的路径，所以终点还是 $p_0$。

---

实际上，更系统的计数方式是：

对于给定的目标终点 $i$，考虑哪些 $(a,b)$ 能使终点为 $i$。

---

逆推思路

终点为 $i$ 的条件：
存在某个 $a,b$，使得 1 走 $K$ 步到 $i$。

想象从 $i$ 倒推 $K$ 步找起点 1 在反图的位置。
反图上，$i$ 的前驱是那些指向 $i$ 的点。但图不是树，所以可能多个前驱。

---

设 $f(u,m)$ 表示从 $u$ 出发走 $m$ 步到达的点（原图方向）。
我们要 $f'(a,b; 1, K) = i$，其中 $f'$ 表示修改 $a \to b$ 后的图。

对于 $a$ 不在 1 到 $p_0$ 路径上的情况，$f'(1,K)=p_0$，所以若要等于 $i \neq p_0$，则必须 $a$ 在原路径上。

所以只需考虑 $a$ 在原路径 $1\to p_0$ 的某个前缀位置。

---

路径表示

设原路径序列： $ P_0=1, P_1, P_2, \dots, P_{d_{\text{enter}}}, \dots $ 进入环后 $P_{d_{\text{enter}}+t} = c_{t \bmod L}$。

记 $P_{K} = p_0$。
设 $a = P_s$，$0 \le s \le K$（但 $s$ 可能很大，不过环上会循环，所以 $a$ 可能是环上某个点）。

当 $a=P_s$ 时，原路径在 $a$ 之后走 $K-s$ 步到 $p_0$。

现在改 $a\to b$，则从 $a$ 走一步到 $b$，再从 $b$ 走 $K-s-1$ 步到某点，该点必须等于 $i$。

所以问题转化为：

对每个 $i$，对每个 $s=0..K$ 且 $P_s$ 有意义（因为 $K$ 很大，$P_s$ 在环上循环），找 $b$ 使得 $\text{从 } b \text{ 出发走 } K-s-1 \text{ 步到达 } i。$

---

周期处理

因为 $K$ 很大，$s$ 也大。设 $T = K-s-1$。
对固定的 $b$，从 $b$ 出发走 $T$ 步会进入一个环 $C_b$，环长 $L_b$。

设从 $b$ 走 $d_b$ 步进入环，环入口节点 $e_b$（环上位置 0）。
则走 $T$ 步时，若 $T \ge d_b$，则最终在环上位置 $(T-d_b) \bmod L_b$。

所以要求： $ \text{环入口 } e_b \text{ 再走 } (T-d_b) \bmod L_b \text{ 步到达 } i。 $ 即 $i$ 必须与 $e_b$ 在同一个环 $C_b$ 上，且环上从 $e_b$ 到 $i$ 的距离（有向）等于 $(T-d_b) \bmod L_b$。

---

最终算法（无代码描述）

1. 预处理原图：找出所有环、环长、每个点走若干步到的环上位置。
2. 原终点 $p_0$：直接模拟或倍增找 $K$ 步位置。
3. 枚举可能的 $a$：由于 $K \ge N$，实际上 $a$ 可以是任何点，但只有某些 $a$ 使得 $s = \text{dist}(1,a) \le K$ 且 $a$ 在路径上才会改变终点。 进一步，若 $a$ 不在 1 可达点，则改它无影响，终点还是 $p_0$。
4. 对每个 $a$ 计算 $T = K - \text{dist}(1,a) - 1$：
   • 若 $T < 0$，不可能（因为 $K$ 大，不会发生）。
   • 否则，枚举 $b$ 使得从 $b$ 走 $T$ 步到达 $i$。由于 $T$ 极大，最终位置只由 $b$ 所在环决定。
5. 对环分类：每个环 $C$ 长 $L$，环上节点 $q_0,\dots,q_{L-1}$。
   从环上某点 $q_j$ 走 $t$ 步到达 $q_{(j+t)\bmod L}$。 所以从 $b$ 走 $T$ 步到达 $i$ 的条件化为：
   • $i$ 在环 $C$ 上，设环上位置 $pos_i$。
   • 从 $b$ 出发走 $d_b$ 步到环入口 $e_b$，设环上位置 $pos_{e_b}$。
   • 要求 $pos_i = (pos_{e_b} + (T-d_b)) \bmod L$。 即 $pos_{e_b} = (pos_i - (T-d_b)) \bmod L$。

于是 $b$ 满足：$b$ 走 $d_b$ 步到环上位置 $pos_{e_b}$（该式由 $i,T$ 定出）。

所以可以预先计算每个环上位置有哪些 $b$（通过反向边传播）。

---

这样我们就能对每个 $i$ 计数 $(a,b)$：

• 固定 $a$ 得 $T$。
• 由 $i,T$ 确定目标环上位置 $pos_{e_b}$。
• 该位置对应的 $b$ 集合已知，大小加进答案。

注意 $a$ 可以等于 $b$，也允许改到原来的目的地。

---

最后一步：$a$ 不在 1 可达点

此时终点总是 $p_0$，所以这些 $(a,b)$ 全贡献给 $i=p_0$ 的答案。

---

总结

本题核心是：

1. 基环树的结构分析。
2. 利用 $K$ 大的性质，将步数取模转化为环上位置问题。
3. 通过反向预处理，对每个 $i$ 快速计算符合条件的 $b$ 的数量，并结合 $a$ 的条件计数。

尽管 $K$ 极大，但 $N$ 较小，我们利用环长不超过 $N$，将大 $K$ 步数取模处理，从而在 $O(N)$ 或 $O(N \log N)$ 复杂度完成计数。