Editorial - AtCoder Grand Contest 063

Contest Duration: 2023-07-30 21:00:00+0900 - 2023-07-31 00:00:00+0900 (local time) (180 minutes) Back to Home

Official

E - Child to Parent Editorial by evima

Hints → https://atcoder.jp/contests/agc063/editorial/6881

In the following, a “way to perform operations” refers to a way of determining the number of times each vertex is selected, and the order of operations does not matter. Additionally, an “operation in subtree $v$” refers to an operation such that $i$ and $P_i$ are both contained in the subtree $v$.

We also write $a_i$ as the initial value of $A_i$ given as input.

[1] Tree DP and polynomial representation

This problem can be solved using a natural tree DP if we ignore the computational complexity. First, we review how to do this. We decompose the process and define several DP tables as follows.

$\mathrm{dp}_1[v][k]$: The number of ways to perform operations in subtree $v$ such that $A_v$ is subject to $+r$ exactly $k$ times.
$\mathrm{dp}_2[v][k]$: The number of ways to perform operations in subtree $v$ such that $A_v$ gets exactly $+k$ in total.
$\mathrm{dp}_3[v][k]$: The number of ways to perform operations in subtree $v$ that result in $A_v=k$.
$\mathrm{dp}_4[v][k]$: The number of ways to perform operations in subtree $v$ and from vertex $v$ to $P_v$ such that $A_v$ is subject to $-1$ exactly $k$ times.

These are computed as follows. Let $\mathrm{ch}(v)$ be the set of all children of $v$.

$\mathrm{dp}_1[v]$ is the convolution of $\mathrm{dp}_4[w]$ for all $w\in \mathrm{ch}(v)$.
$\mathrm{dp}_2[v][rk] = $\mathrm{dp}_1[v][k]$.
$\mathrm{dp}_3[v][a_v+k] = \mathrm{dp}_2[v][k]$.
$\mathrm{dp}_4[v][k] = \sum_{i\geq k}\mathrm{dp}_3[v][i]$.

Since the convolution comes up, we will use polynomials instead of arrays. Let $F_{v,1}(x) = \sum_{k}\mathrm{dp}[v][k]x^k$. $F_{v,2}(x)$, $F_{v,3}(x)$, and $F_{v,4}(x)$ are defined similarly. Then, the above calculation can be expressed as follows.

$F_{v,1}(x) = \prod_{w\in\mathrm{ch}(v)}F_{w,4}(x)$.
$F_{v,2}(x) = F_{v,1}(x^r)$.
$F_{v,3}(x) = x^{a_v}F_{v,2}(x)$.
$F_{v,4}(x) = F_{v,3}(x)+\dfrac{F_{v,3}(1)-F_{v,3}(x)}{1-x}$.

Only the operation to obtain $F_{v,4}$ from $F_{v,3}$ is a bit non-trivial. It represents a linear operation that replaces $x^k$ with $1+\cdots +x^k$.

We can compute these bottom-up and report $F_{v,3}(1)$ when $v$ is a root.

[2] Using variable transformations

If you try to use the solution in [1] as it is, you will have to keep a huge number of coefficients to compute the answer, which slows you down.

In particular, it is troublesome that the substitution of $x=1$ is considered to obtain the answer and to compute $F_{v,4}$, which makes it impossible to ignore higher-order terms in the polynomials.

Therefore, we consider a variable transformation of the type $G(x)=F(1+x)$. That is, define $G_{v,1}$ as $G_{v,1}(x) = F_{v,1}(1+x)$ and define $G_{v,2}, G_{v,3}, G_{v,4}$ in the same way.

Rewriting the procedure for $F_{v,i}$ with appropriate transformations, we find that $G_{v,i}$ can be computed as follows.

$G_{v,1}(x) = \prod_{w\in\mathrm{ch}(v)}G_{w,4}(x)$.
$G_{v,2}(x) = G_{v,1}((1+x)^r-1)$.
$G_{v,3}(x) = (1+x)^{a_v}G_{v,2}(x)$.
$G_{v,4}(x) = G_{v,3}(x)+\dfrac{G_{v,3}(0)-G_{v,3}(x)}{-x}$.

What we need to find is $G_{v,3}(0)$ when $v$ is a root, i.e. $G_{v,3}(x)\pmod{x^1}$.

It is easy to see that for a positive integer $n$, the following holds.

$G_{v,1}(x)\pmod{x^n}$ is determined from $G_{w,4}(x)\pmod{x^n}$ for $w\in \mathrm{ch}(v)$.
$G_{v,2}(x)\pmod{x^n}$ is determined from $G_{1,v}(x)\pmod{x^n}$.
$G_{v,3}(x)\pmod{x^n}$ is determined from $G_{v,2}(x)\pmod{x^n}$.
$G_{v,4}(x)\pmod{x^n}$ is determined from $G_{v,3}(x)\pmod{x^{n+1}}$.

Note that the exponents are shifted only when obtaining $G_{v,4}$ from $G_{v,3}$.

Thus, at a vertex $v$ of depth $d$, consider finding the following:

$G_{v,1} \pmod{x^{1+d}}$
$G_{v,2} \pmod{x^{1+d}}$
$G_{v,3} \pmod{x^{1+d}}$
$G_{v,4} \pmod{x^{d}}$$

These can be computed bottom-up.

This is faster than the solution described in [1], since only $O(N)$ coefficients are needed at each vertex. With proper implementation of each step, the problem can be solved in $O(N^3)$ time.

Only the computation of $G((1+x)^r-1)$ is a bit difficult, but if you compute $H(x) = G(x-1)$ and then find $H((1+x)^r)$, and use the binomial theorem appropriately, this composition can be computed in $O(d^2)$ time.

[3] Notes

Instead of considering $G(x) = F(x+1)$, one can consider a sequence of higher-order differential coefficients $\bigl(F(1),F'(1),F''(1),\ldots\bigr)$, which will be exactly the same.
Using a sophisticated polynomial algorithm, it can be solved in $O(N^2\log^2 N)$ time. The hardest part would probably be the composite $G((1+x)^r-1)$. This can also be done in $O(d\log^2d)$ time by reducing it to polynomial Taylor shift, compositions with $\exp$ and $\log$, and such.

posted:
last update: