2872. Maximum Number of K-Divisible Components
Difficulty: Hard
Topics: Tree, Depth-First Search
There is an undirected tree with n nodes labeled from 0 to n - 1. You are given the integer n and a 2D integer array edges of lengthn - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.
You are also given a 0-indexed integer array values of length n, where values[i] is the value associated with the ith node, and an integer k.
A valid split of the tree is obtained by removing any set of edges, possibly empty, from the tree such that the resulting components all have values that are divisible by k, where the value of a connected component is the sum of the values of its nodes.
Return the maximum number of components in any valid split.
Example 1:
- Input: n = 5, edges = [[0,2],[1,2],[1,3],[2,4]], values = [1,8,1,4,4], k = 6
- Output: 2
-
Explanation: We remove the edge connecting node 1 with 2. The resulting split is valid because:
- The value of the component containing nodes 1 and 3 is values[1] values[3] = 12.
- The value of the component containing nodes 0, 2, and 4 is values[0] values[2] values[4] = 6.
- It can be shown that no other valid split has more than 2 connected components.
Example 2:
- Input: n = 7, edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], values = [3,0,6,1,5,2,1], k = 3
- Output: 3
-
Explanation: We remove the edge connecting node 0 with 2, and the edge connecting node 0 with 1. The resulting split is valid because:
- The value of the component containing node 0 is values[0] = 3.
- The value of the component containing nodes 2, 5, and 6 is values[2] values[5] values[6] = 9.
- The value of the component containing nodes 1, 3, and 4 is values[1] values[3] values[4] = 6.
- It can be shown that no other valid split has more than 3 connected components.
Constraints:
- 1 <= n <= 3 * 104
- edges.length == n - 1
- edges[i].length == 2
- 0 <= ai, bi < n
- values.length == n
- 0 <= values[i] <= 109
- 1 <= k <= 109
- Sum of values is divisible by k.
- The input is generated such that edges represents a valid tree.
Hint:
- Root the tree at node 0.
- If a leaf node is not divisible by k, it must be in the same component as its parent node so we merge it with its parent node.
- If a leaf node is divisible by k, it will be in its own components so we separate it from its parent node.
- In each step, we either cut a leaf node down or merge a leaf node. The number of nodes on the tree reduces by one. Repeat this process until only one node is left.
Solution:
We can implement a Depth-First Search (DFS) approach to explore the tree, track the values of components, and find the maximum number of valid splits.
Key Points:
- Tree Structure: We are working with an undirected tree where each node has an associated value. We need to find the maximum number of connected components we can get by splitting the tree such that the sum of values of each component is divisible by k.
- DFS Traversal: We use Depth-First Search (DFS) to traverse the tree and calculate the subtree sums.
- Divisibility Check: After calculating the sum of a subtree, if it's divisible by k, it means the subtree can be considered as a valid component by itself.
- Edge Removal: By removing edges that connect nodes whose subtree sums aren't divisible by k, we can maximize the number of valid components.
Approach:
- Tree Representation: Convert the edges list into an adjacency list to represent the tree.
- DFS Traversal: Start from node 0 and recursively calculate the sum of values in each subtree. If the sum is divisible by k, we can cut that subtree off from its parent, effectively forming a valid component.
- Global Count: Maintain a global counter (result) that tracks the number of valid components formed by cutting edges.
- Final Check: At the end of the DFS traversal, ensure that if the root's total subtree sum is divisible by k, it counts as a valid component.
Plan:
- Input Parsing: Convert the input into a usable form. Specifically, create an adjacency list representation for the tree.
- DFS Function: Write a recursive function dfs(node) that computes the sum of values in the subtree rooted at node. If this sum is divisible by k, increment the result counter and "cut" the edge by returning 0 to prevent merging back into the parent.
- Start DFS from Root: Call dfs(0) and then check the final value of result.
Solution Steps:
- Build the Tree: Convert the edge list into an adjacency list for easier traversal.
- Initialize Visited Array: Use a visited array to ensure we don't revisit nodes.
- DFS Traversal: Perform DFS starting from node 0. For each node, calculate the sum of values of its subtree.
- Check Divisibility: If the sum of a subtree is divisible by k, increment the result and reset the subtree sum to 0.
- Final Component Check: After the DFS traversal, check if the entire tree (rooted at node 0) has a sum divisible by k and account for it as a separate component if necessary.
Let's implement this solution in PHP: 2872. Maximum Number of K-Divisible Components
Explanation:
- Tree Construction: We build an adjacency list to represent the tree structure. Each edge connects two nodes, and we use this adjacency list to traverse the tree.
- DFS Traversal: The DFS function recursively calculates the sum of the subtree rooted at each node. If the sum of the subtree is divisible by k, we increment the result and consider the subtree as a separate valid component.
- Returning Subtree Sum: For each node, the DFS function returns the sum of values for its subtree. If a subtree is divisible by k, we effectively "cut" the edge by returning a sum of 0, preventing further merging back with the parent node.
- Final Check: At the end of the DFS, we ensure that if the sum of the entire tree is divisible by k, it counts as a valid component.
Example Walkthrough:
Example 1:
Input:
- n = 5, edges = [[0,2],[1,2],[1,3],[2,4]], values = [1,8,1,4,4], k = 6.
DFS starts from node 0:
- Node 0: subtree sum = 1
- Node 2: subtree sum = 1 1 4 = 6 (divisible by 6, so we can cut this edge)
- Node 1: subtree sum = 8 4 = 12 (divisible by 6, cut this edge)
- Final count of components = 2.
Example 2:
Input:
- n = 7, edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], values = [3,0,6,1,5,2,1], k = 3.
DFS starts from node 0:
- Node 0: subtree sum = 3
- Node 2: subtree sum = 6 2 1 = 9 (divisible by 3, cut this edge)
- Node 1: subtree sum = 0 5 = 5 (not divisible by 3, merge this sum)
- Final count of components = 3.
Time Complexity:
- DFS Time Complexity: O(n), where n is the number of nodes. We visit each node once and perform constant-time operations at each node.
- Space Complexity: O(n) for the adjacency list, visited array, and recursion stack.
Thus, the overall time and space complexity is O(n), making this approach efficient for the given problem constraints.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
- GitHub
The above is the detailed content of Maximum Number of K-Divisible Components. For more information, please follow other related articles on the PHP Chinese website!

Hot AI Tools

Undress AI Tool
Undress images for free

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Clothoff.io
AI clothes remover

Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

Hot Tools

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Hot Topics











TosettherighttimezoneinPHP,usedate_default_timezone_set()functionatthestartofyourscriptwithavalididentifiersuchas'America/New_York'.1.Usedate_default_timezone_set()beforeanydate/timefunctions.2.Alternatively,configurethephp.inifilebysettingdate.timez

ToquicklytestaPHPcodesnippet,useanonlinePHPsandboxlike3v4l.orgorPHPize.onlineforinstantexecutionwithoutsetup;runcodelocallywithPHPCLIbycreatinga.phpfileandexecutingitviatheterminal;optionallyusephp-rforone-liners;setupalocaldevelopmentenvironmentwith

Upgrading the PHP version is actually not difficult, but the key lies in the operation steps and precautions. The following are the specific methods: 1. Confirm the current PHP version and running environment, use the command line or phpinfo.php file to view; 2. Select the suitable new version and install it. It is recommended to install it with 8.2 or 8.1. Linux users use package manager, and macOS users use Homebrew; 3. Migrate configuration files and extensions, update php.ini and install necessary extensions; 4. Test whether the website is running normally, check the error log to ensure that there is no compatibility problem. Follow these steps and you can successfully complete the upgrade in most situations.

TosetupaPHPdevelopmentenvironmentonLinux,installPHPandrequiredextensions,setupawebserverlikeApacheorNginx,testwithaPHPfile,andoptionallyinstallMySQLandComposer.1.InstallPHPandextensionsviapackagemanager(e.g.,sudoaptinstallphpphp-mysqlphp-curlphp-mbst

To set up a PHP development environment, you need to select the appropriate tools and install the configuration correctly. ①The most basic PHP local environment requires three components: the web server (Apache or Nginx), the PHP itself and the database (such as MySQL/MariaDB); ② It is recommended that beginners use integration packages such as XAMPP or MAMP, which simplify the installation process. XAMPP is suitable for Windows and macOS. After installation, the project files are placed in the htdocs directory and accessed through localhost; ③MAMP is suitable for Mac users and supports convenient switching of PHP versions, but the free version has limited functions; ④ Advanced users can manually install them by Homebrew, in macOS/Linux systems

To merge two PHP arrays and keep unique values, there are two main methods. 1. For index arrays or only deduplication, use array_merge and array_unique combinations: first merge array_merge($array1,$array2) and then use array_unique() to deduplicate them to finally get a new array containing all unique values; 2. For associative arrays and want to retain key-value pairs in the first array, use the operator: $result=$array1 $array2, which will ensure that the keys in the first array will not be overwritten by the second array. These two methods are applicable to different scenarios, depending on whether the key name is retained or only the focus is on

TopreventCSRFattacksinPHP,implementanti-CSRFtokens.1)Generateandstoresecuretokensusingrandom_bytes()orbin2hex(random_bytes(32)),savethemin$_SESSION,andincludetheminformsashiddeninputs.2)ValidatetokensonsubmissionbystrictlycomparingthePOSTtokenwiththe

To determine the strength of the password, it is necessary to combine regular and logical processing. The basic requirements include: 1. The length is no less than 8 digits; 2. At least containing lowercase letters, uppercase letters, and numbers; 3. Special character restrictions can be added; in terms of advanced aspects, continuous duplication of characters and incremental/decreasing sequences need to be avoided, which requires PHP function detection; at the same time, blacklists should be introduced to filter common weak passwords such as password and 123456; finally it is recommended to combine the zxcvbn library to improve the evaluation accuracy.
