idea, data, solution, std from Ecrade_
引理 1：不移动到子树内没有黑点的结点一定不劣。
我们的目标是遍历到所有黑点，而移动到子树内没有黑点的结点只会徒增操作次数。
引理 2：当移动到结点 $u$ 的子树内时，遍历完 $u$ 子树内的所有黑点再移动到 $u$ 的子树外一定不劣。
若未遍历完 $u$ 子树内的所有黑点就移动到了 $u$ 的子树外，则后面仍需再次移动到 $u$ 子树内遍历剩下的黑点，而这显然只会徒增操作次数。
引理 3：去除子树内没有黑点的结点后得到一棵新树，那么沿着新树的某种欧拉序移动一定不劣。
不妨令红点表示当前未遍历完子树内所有黑点的结点，绿点反之。
根据引理 1，去除子树内没有黑点的结点不会造成任何影响。
根据引理 2，若当前棋子在红点处，则棋子只能往下移动（即移动到深度更大的结点处）。
若当前棋子在绿点 $u$ 处，则考虑离 $u$ 最近且为红点的祖先结点 $r$。
根据引理 2，棋子接下来只能移动到 $r$ 子树内的某个黑点。
观察到在移动的过程中，棋子必然会经过 $r$ 或 $r$ 的某个子结点。
那么在从 $u$ 移动到 $r$ 或 $r$ 的某个子结点的过程中，由于路径上除了 $r$ 为红点，其余均为绿点，故一直往上移动是最优的。
接着，在到达 $r$ 或 $r$ 的某个子结点后，棋子必然又在红点处，这时只能往下移动了。
移动到最后一个黑点后，显然我们一直往上移动至根节点即可。
所以，在整个过程中，我们发现棋子是不会走“回头路”的，其实这也是沿着欧拉序移动的充要条件。
引理 4：沿着新树的欧拉序移动一定是所有移动路径中总路程最短的。
显然，我们必须要经过所有新树的叶结点。
所以，每条边都需要被经过至少两次，而沿着欧拉序移动恰能达到这个理论下界。
注意到总路程 $l$ 为定值（新树边数的两倍），若第二种操作进行了 $x$ 次，则总操作次数为 $x+(l-2x)=l-x$。
所以，我们仅需知道 $x$ 在无限制的情况下的最大值 $x_{\text{max}}$ 即可，这样对于每个询问，答案即为 $l-\min(k,x_{\text{max}})$。
考虑使用动态规划计算出 $x$ 取到最大值时的操作次数。
定义 $f_{u,0/1,0/1}$ 表示进入结点 $u$ 的子树内时，棋子处在 $u/u$ 的某个子结点处；遍历完 $u$ 子树内所有黑点后，将要从 $u/u$ 的某个子结点移动到 $u$ 子树外的操作次数。
由于 $f_{u,0,1}$ 和 $f_{u,1,0}$ 的情况是对称的，故我们仅考虑 $f_{u,1,0}$。
对于 $u$ 的所有子结点，我们需找到一个合适的遍历顺序，使得依次拼接后操作次数最少。
容易发现，相邻两个子结点分别是 $0$ 出和 $0$ 进时，则中间只需进行一次操作，而其余情况则需进行两次操作，故一个直观的想法是 $0$ 越多越好。
考虑贪心。
一般情况下，当 $f_{v,0,0}\le f_{v,0,1}$ 时，取 $f_{v,0,0}$ 不劣。
一般情况下，当 $f_{v,0,0}>f_{v,0,1}$ 时，取 $f_{v,0,1}$ 不劣。
$f_{v,0,1}$ 和 $f_{v,1,1}$ 同理。
所以我们得出结论：一般情况下，对于 $f_{v,0,0},f_{v,0,1},f_{v,1,0}$，哪个最小就取哪个，若有多个最小值，则哪个含 $0$ 越多就取哪个。
至于这里的结论为什么只适用于一般情况下，后续会提及。
子结点与子结点之间的拼接情况已处理完，最后仅剩下首尾两处根结点与子结点之间的情况了。
显然，当根结点 $u$ 和子结点 $v$ 分别满足 $1$ 进和 $0$ 进或是 $1$ 出和 $0$ 出，即进/出 $u$ 子树时处在的结点恰为 $v$ 时，便不需要进行操作，而其余情况则需进行一次操作。
仍考虑贪心。
首尾两处与子结点均需进行一次操作，而中间相邻子结点之间分别满足 $0$ 出和 $0$ 进的数量越多越好。
当没有 $0$ 进 $1$ 出或 $1$ 进 $0$ 出的子结点时，只能将所有 $0$ 进 $0$ 出的子结点紧挨着排，后跟着所有 $1$ 进 $1$ 出的子结点；
否则将一个 $1$ 进 $0$ 出的子结点排在首位，后跟着所有 $0$ 进 $0$ 出的子结点，再跟着 $0$ 进 $1$ 出、 $1$ 进 $0$ 出的交替排列，最后跟着所有 $1$ 进 $1$ 出的子结点。
将所有 $0$ 进 $0$ 出的子结点紧挨着排，后跟着 $0$ 进 $1$ 出、 $1$ 进 $0$ 出的交替排列，最后跟着所有 $1$ 进 $1$ 出的子结点。
若 $u$ 仅有一个子结点，暴力考虑所有情况即可；
否则将所有 $0$ 出 $0$ 进的子结点紧挨着排，后跟着 $0$ 出 $1$ 进、 $1$ 出 $0$ 进的交替排列，再后跟着所有 $1$ 出 $1$ 进的子结点，最后跟一个 $1$ 出 $0$ 进的的子结点。
注意这里需要再考虑强制将所有子结点变为 $0$ 进 $0$ 出的子结点的情况，因为这时的贪心可能就不奏效了。注意此时若 $u$ 为黑点则需中途再进行一次操作去遍历 $u$。
至此，我们便用 $O(\sum n+\sum q)$ 时间复杂度解决了本题。
idea, data, solution, std from JohnVictor
算法一（暴力）
直接 $\text{DP}$，复杂度 $O(n^2)$，可以通过第一个子任务。
算法二（部分分）
输出 $0$ 可以通过第二个子任务。第三个子任务的答案可以用一些组合数简单表示。对于第四个子任务，可以看做 $O(np)$ 个点加一个下三角，下三角部分的贡献可以简单反射容斥计算，剩下部分暴力即可。第五个子任务留给小常数 $O(n\sqrt {n \log n})$ 的直接分块 $\text{NTT}$ 和大常数正解。
算法三（正解）
下面的分析中，令块长 $B=p$。
考虑平移指数基。具体地，对于每一列，考虑维护一个形如 $P(x)/(1-x)^k$ 的多项式表示一整列的 $\text{DP}$ 值构成的生成函数。
我们要支持的操作是加一个单项式，查询一项系数（这两个操作足以解决每一列有一个不能走的点的问题），将 $k$ 加上 $1$（也就是一次前缀和）。
考虑定期重构。我们维护 $P(x)(1-x)^k$ 的形式。每一次将 $k$ 减小 $1$，变成了 $0$ 就重构。这样，对于这个形式查询一项系数是 $O(B)$ 的。
利用 $1-x^p=(1-x)^p$，重构的时候只用除以 $(1-x^B)$，这个相当于隔 $B$ 个做一次前缀和，复杂度 $O(n)$。
主要的问题是加一个单项式之后再除以 $(1-x)$ 怎么办。这个只用额外维护成 $P(x)(1-x)^k+Q(x)/(1-x)^k$ 即可。注意这里的系数还是可以 $O(k)$ 来计算的，因为 $Q$ 不超过 $k$ 个非零系数，单个贡献可以 $O(1)$。
所以现在的复杂度为 $\mathcal O(np+\frac {n^2}{p})$，可以通过所有子任务。
算法四
考虑每 $p$ 条斜线（即 $i+j=t\times p$ 的位置 $(i,j)$）算一次 dp 值。转移的时候可以考虑对障碍点容斥，钦定一些障碍点被经过了，并对可能产生转移的两个障碍点之间计算贡献。
斜线 -> 斜线的贡献可以 $\mathcal O(\frac{n^2}{p})$ 处理；障碍点 -> 障碍点，斜线 -> 障碍点和 障碍点 -> 斜线的贡献均可以 $\mathcal O(np)$ 处理。
时间复杂度 $\mathcal O(np+\frac {n^2}{p})$。
idea, data, solution, std from zhoukangyang. sol-114514,-1919810 from bulijiojiodibulido
APIO2024 会讲的。大家可以提前复习一下积性函数相关知识。UPD：apio 讲课的核心内容放在了 这里
算法 -114514,-1919810 是 bulijiojiodibulido 老师验题时用的做法，算法一、算法二是官方题解做法。
算法 -114514
令 $t=\gcd(i, j)$，如果我们提取 $i$ 和 $j$ 中与 $t$ 相关的所有因子，即令 $i = t_is_i, j =t_js_j$，其中 $\gcd(t_i, s) = \gcd(t_j, s) = 1$。那么有 $f(ij) = f(s_i) f(s_j) f(t_i t_j)$。
所以可以考虑枚举 $t_i, t_j$，满足它们有相同的素因子分布（即 $\text{rad}(t) = \text{rad}(t_i) = \text{rad} (t_j)$，其中 $\text{rad}(n) = \prod_{p|n} p$），然后计算上式。这个时候我们还有 $\gcd(s_i, t) = \gcd(s_j, t) = 1$ 的条件，如果直接反演，那么复杂度比较高。
类似构造系数 $g(y_i, y_j)$，满足 $\sum_{x_i|y_i, x_j | y_j, \text{rad} (x_i) = \text{rad} (x_j)} g(x_i, x_j) = f(x_ix_j)$。令 $F(n) = \sum_{i=1}^n f(i)$。那么答案为 $$\sum_{t_i,t_j ,\text{rad}(t_i) = \text{rad} (t_j)} g(t_i, t_j) F(\lfloor{n/t_i\rfloor}) F(\lfloor{n/t_j\rfloor})$$。因为我们能保证每对 $t_i, t_j$，前面加的总系数为 $f(t_i t_j)$。
对于函数 $g$，在上面等式中，右侧是积性，也就是关于每个素因子是独立的，所以 $g$ 的取值也是对于每个素因子都是独立的。所以只需要对于所有素数，预处理出 $g(p^i, p^j)$ 的值（事实上是一个次数为 $2(i+j)$ 的多项式），那么对于任意两个数，可以快速算出上述的 $g$ 值。
这个时候直接枚举 $t_i, t_j$，也就是从小到大枚举每个素数，以及在 $t_i, t_j$ 中的指数就能快速计算答案。枚举代价为 $1$ 到 $n$ 内所有 $\text{rad}$ 相同的数字的对数，好像是 $O(n)$ 级别的，可以通过 $3\times 10^7$ 的数据。
算法 -1919810
考虑如何加速这个过程，我们希望能快速计算出比较大的素数的贡献。
$dp_{n_1, n_2, p}$ 表示从大到小枚举因子到 $p$，$n_1 = \lfloor{n/t_i\rfloor}, n_2 = \lfloor{n/t_j\rfloor}$，$g$ 的乘积。对于大于 $\sqrt{n}$ 的素数，它一定是从 $(n, n)$ 转移向 $(\lfloor n/p \rfloor, \lfloor n/p \rfloor)$，并且乘上的是一个四次多项式。
那么我们只需要预处理 $\lfloor n/p \rfloor$ 相同的每段的素数的四次多项式的值，就可以快速完成这些素数的转移。对于剩下的素数，我们枚举它们的指数，从大到小转移即可。
如果使用记忆化，当 $n=10^9$ 的时候，状态数大概在 $2\times 10^6$ 级别，转移大概在 $2\times 10^8$ 级别，使用精细的实现卡常数就可以通过。
实际大部分的状态都是在小素数的地方，所以可能可以从小素数枚举然后 meet in the middle，但是没编出来。
算法一
考虑把积性函数推广至二维，如果函数 $f(x,y)$ 是二维积性函数，假设 $p_i$ 是从小到大第 $i$ 个质数，$x=\prod_i p_i^{a_i}$，$y=\prod_i p_i^{b_i}$，那么 $f(x,y) = \prod_{i} f(p_i^{a_i},p_i^{b_i})$。容易发现我们要求的是二维积性函数前缀和。
考虑设计积性函数 $g(x,y)$ 满足 $g(p^{a},p^b) = f(p^a,1) f(1,p^b)$。对于这个函数，其前缀和 $\sum_{i\le n_1} \sum_{j\le n_2} f(i,1)f(1,j)$ 是相当容易计算的。观察 $h=f/g$。我们发现 $h(p^k,1) = h(1,p^k) = 0$。
暴力枚举 $h$ 有值的位置，可以证明复杂度是 $\mathcal O(n)$。期望得分 $70$ 分。
算法二
考虑优化之前的算法，设计二维积性函数 $g_3$ 满足 $g_3$ 只在 $g_3(x,x)$ 处有值且值为 $h(x,x)$，接下来令 $h' = h/g_3$。
此时有值的 $h'(p^a,p^b)$（$p\in \mathbb{P}, a,b\ge 0$，$a+b\neq 0$）就满足 $a,b\ge 1$ 且 $a\neq b$ 了。
接下来暴力枚举 $h'$ 中的有值元素 $(x,y)$，计算 $\sum_{u \le n/x,v\le n/y} (g * g_3) (u,v)$，把这些答案带上系数加起来就能得到最终答案了。
而 $\sum_{i=1}^A \sum_{j=1}^{B} (g * g_3)(u,v) = \sum_{k=1}^{\min(A,B)} g_3(k,k) \sum_{i=1}^{A/k}\sum_{j=1}^{B/k} g(i,j)$。暴力整出分块计算答案。
我们当然要筛 $f(x,1)$ 和 $g_3(x,x)$ 的块筛前缀和。可以证明，除此之外的复杂度不超过 $\mathcal O(n^{2/3}\log n)$。
其实还可以更快一点，不过没必要了。
鄂公网安备 42010202000505 号