题解：CF1778F Maximizing Root

· · 题解

提供一个自顶向下的做法，不是 DP。加上快读后可以跑到 Rank 1。

定义

定义 \text{subGcd}(v) 为子树 v 所有数（点权）的 GCD。

定义 \text{ceilSqrt}(x) 为最小的 c，满足 c^2 是 x 的倍数。这可以通过把 x 分解质因数，每个质因子的幂次 e 改成 \lceil e/2 \rceil 得到。

思考

  1. 既然要让答案最大，每次操作选的 x 应当是子树所有数的 GCD。
  2. 按照从叶子到根的顺序操作，可以让答案尽量大。例如从上到下是 16,4,2，先操作上面，只能把 16 乘以 2；先操作下面，最后可以让 16 乘以 16。
  3. 答案一定是 a_1 乘以它的一个因子。由于 1000 以内的数至多有 32 个因子（例如 840），所以我们可以从大到小地枚举 a_1 的因子 d。如果 1 的每个儿子子树都能通过操作（操作次数之和小于 k），使得子树所有数的 GCD 是 d 的倍数，那么答案就是 a_1\cdot d。
  4. 写一个自顶向下的 DFS，额外传入参数 d。考虑 1 的儿子 v，分类讨论：
    1. 如果 \text{subGcd}(v) 已经是 d 的倍数，那么无需操作子树 v 中的任何节点。
    2. 否则，如果 \text{subGcd}(v)^2 是 d 的倍数，那么只需要在节点 v 上操作一次，无需操作更下面的节点。
    3. 否则，如果 v 是叶子，或者 a_v^2 不是 d 的倍数，那么无法完成操作。
    4. 否则，应该先操作 v 的后代，然后操作 v。我们的目标是，对于 v 的每个儿子子树 w，通过操作，使得 \text{subGcd}(w) 是 \text{ceilSqrt}(d) 的倍数，这样就可以让 \text{subGcd}(v)^2 是 d 的倍数。这个结论是本题的核心结论。根据该结论，继续往下递归 v 的儿子 w，额外传入参数 \text{ceilSqrt}(d)。
  5. 累加 DFS 中的操作次数。如果操作次数小于 k（注意不是小于等于，因为最后还要对节点 1 操作一次），那么答案就是 a_1\cdot d。

细节：特判 k=0 的情况。

Go 语言代码（下标从 0 开始）：

package main
import ("bufio";."fmt";"os")
func gcd(a, b int) int { for a != 0 { a, b = b%a, a }; return b }

func main() {
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()

    const mx = 1000
    divisors := [mx + 1][]int{}
    for i := mx; i > 0; i-- { // 方便后面从大到小遍历因子
        for j := i; j <= mx; j += i {
            divisors[j] = append(divisors[j], i)
        }
    }

    // ceilSqrt[i]^2 是 i 的倍数
    ceilSqrt := [mx + 1]int{}
    for i := 1; i <= mx; i++ {
        ceilSqrt[i] = 1
        x := i
        for p := 2; p*p <= x; p++ {
            for p2 := p * p; x%p2 == 0; x /= p2 {
                ceilSqrt[i] *= p
            }
            if x%p == 0 {
                ceilSqrt[i] *= p
                x /= p
            }
        }
        if x > 1 {
            ceilSqrt[i] *= x
        }
    }

    var T, n, k int
    for Fscan(in, &T); T > 0; T-- {
        Fscan(in, &n, &k)
        a := make([]int, n)
        for i := range a {
            Fscan(in, &a[i])
        }
        g := make([][]int, n)
        for i := 1; i < n; i++ {
            var v, w int
            Fscan(in, &v, &w)
            v--
            w--
            g[v] = append(g[v], w)
            g[w] = append(g[w], v)
        }
        if k == 0 {
            Fprintln(out, a[0])
            continue
        }

        subGcd := make([]int, n)
        var dfs0 func(int, int)
        dfs0 = func(v, fa int) {
            subGcd[v] = a[v]
            for _, w := range g[v] {
                if w != fa {
                    dfs0(w, v)
                    subGcd[v] = gcd(subGcd[v], subGcd[w])
                }
            }
        }
        dfs0(0, -1)

        var cnt int
        var dfs func(int, int, int)
        dfs = func(v, fa, d int) {
            if subGcd[v]%d == 0 {
                // 无需操作
                return
            }
            if subGcd[v]*subGcd[v]%d == 0 {
                cnt++ // 操作 v
                return
            }
            if len(g[v]) == 1 || a[v]*a[v]%d > 0 {
                cnt = 1e9 // 无法操作
                return
            }
            for _, w := range g[v] {
                if w != fa {
                    dfs(w, v, ceilSqrt[d])
                }
            }
            cnt++ // 操作 v
        }

        for _, d := range divisors[a[0]] {
            cnt = 0
            for _, v := range g[0] {
                dfs(v, 0, d)
            }
            if cnt < k {
                Fprintln(out, a[0]*d)
                break
            }
        }
    }
}

时间复杂度：\mathcal{O}(Dn)，其中 D=32。

欢迎关注 B站@灵茶山艾府