E：
考虑维护当前所在位置的指针。
设当前点为 \(u\)。
对于第一个操作，我们可以将 \(u\) 新增一个儿子 \(x\)，并将指针转移到 \(x\)。
对于第二个操作，把指针转移到 \(fa_u\) 即可。
对于第三个操作，我们可以开一个 map，将点 \(u\) 放到编号为 \(x\) 的 map 中。
对于第四个操作，将指针转移到 \(map_x\) 即可。
时间复杂度 \(\mathcal O(Q\log Q)\)。
F：
离散化后区间 DP，类似关路灯。
G：
如果 \(\sum R_i\ne \sum C_i\)，显然答案是 \(0\)。
接下来假设都满足 \(\sum R_i=\sum C_i\)。
我们一行一行的填下去，当填到第 \(i\) 行的时候，需要满足以下条件：
- \(\sum_{j=1}^N A_{i,j}=R_i\)
- \(\forall j,C^{′}_{i,j}=C_j-\sum_{k=1}^{i}A_{k,j}\ge0\)
\(C^{′}_{i,j}\) 就是填到第 \(i\) 行第 \(j\) 列还能填的。
注意到最终合法的状态就是填完 \(N\) 行之后所以的 \(C^{′}_{N,j}\) 都为 \(0\)。
设 \(f_{i,x}\) 表示填了前 \(i\) 行并且目前有 \(x\) 列 \(j\) 满足 \(C^′_{i,j}=2\) 的方案数。
设 \(y\) 为目前有 \(y\) 列 \(j\) 满足 \(C^′_{i,j}=1\)。
则有
\[\sum_{j=1}^N C^′_{i,j}=y+2x \]那么
\[y=\sum_{j=1}^N C^′_{i,j}-2x \]\[\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_{j=1}^N (C_j-\sum_{k=1}^iA_{k,j})-2x \]\[\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_{j=1}^N C_j-\sum_{j=1}^N\sum_{k=1}^iA_{k,j}-2x \]\[\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_{j=1}^N C_j-\sum_{k=1}^i\sum_{j=1}^NA_{k,j}-2x \]\[\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_{j=1}^NC_j-\sum_{k=1}^iR_k-2x \]所以 \(y\) 就能用 \(x\) 表示了。
设 \(x_0\) 表示 \(j\) 的数量满足 \(C^′_{0,j}=C_j=2\)。
则一开始 \(f_{0,x_0}=1\)，其余均为 \(0\)。
然后考虑转移。
如果 \(R_i=0\)，则有
\[f_{i,x}=f_{i-1,x-1} \]如果 \(R_i=1\)，则有
\[f_{i,x}=f_{i-1,x+1}\times (x+1)+f_{i-1,x}\times (y+1) \]如果 \(R_i=2\)，则有
\[f_{i,x}=f_{i-1,x+1}\times (x+1)+f_{i-1,x+2}\times \binom{x+2}{2}+f_{i-1,x}\times \binom{y+2}{2}+f_{i-1,x+1}\times (x+1)y \]最终答案就是 \(f_{N,0}\)。
时间复杂度 \(\mathcal O(N^2)\)。
标签：map,Code,sum,2x,times,ABC273,指针 From： https://www.cnblogs.com/Kobe303/p/16856590.html