2872.md

2872. Maximum Number of K-Divisible Components

Leetcode link

题目简介

本题是个 hard，而且题目特别长，看的人晕头转向的，我这边先简单描述一下题目给的参数都是干嘛的：

• n：代表题目给的树有几个节点
• edges：是一个二维数组，数组的每一项有两个节点，代表这两个节点之间有边
• values：是一个数组，每一项代表当前下标对应的节点的值
• k：一个 number，作用后面会将

通过前三个参数，我们可以画出一棵树出来，题目要求我们可以任意斩断树节点之间的连接，但是前提是斩断的两边的节点只和，都要能够被 k 整除，并且题目要求我们求出最多能够切成多少个

解题思路

这种要把树分开的题目，一般都需要遍历树，这题主要有两个难点：

1. 如何根据前三个参数把树构建出来
2. 如何根据自己构建的树，通过遍历将其拆分成尽可能多的树枝

首先第一个难点，我们可以通过自己构建一个简单的二维数组来表示一棵树，这个二维数组的长度是 n，而二维数组内部储存的数组则表示与当前数组下标节点有存在边的节点

举个例子：[[1,2], [0], [0]] 表示节点 0 有两条边，分别连接到了节点 1 与节点 2，而节点 1 只与节点 0 相连；同理节点 2 也只与节点 0 相连

0
|  \
1   2

然后，第二步就是要看要如何遍历这颗树

我们可以从叶子节点开始思考，有两种可能：

1. 如果当前叶子节点能够被 k 整除，那么我们就可以将其与其父节点的连接斩断
2. 如果当前叶子节点不能被 k 整除，那么我们要将它的值往其父节点累加，直到累加的值可以被 k 整除，再将整棵子树与其他树的连接切断

这种往父节点累加的遍历，自然而然就想到了 dfs

于是我们就得到了代码：

Javascript

/**
 * @param {number} n
 * @param {number[][]} edges
 * @param {number[]} values
 * @param {number} k
 * @return {number}
 */
var maxKDivisibleComponents = function (n, edges, values, k) {
    let result = 0

    // first step: create the tree
    const tree = Array.from(new Array(n), () => new Array())
    edges.forEach(([n1, n2])=>{
        tree[n1].push(n2)
        tree[n2].push(n1)
    })

    // second step: dfs
    const dfs = (node, parent) => {
        let sum = values[node]

        for(const pair of tree[node]) {
            if(pair === parent) {
                continue
            }
            sum+= dfs(pair, node)
        }

        if(sum % k === 0) {
            result++
        }
        return sum
    }

    // Each node can be the root, we use 0 just for convenience
    dfs(0)
    return result
};