Tap here to switch tabs
Problem
Submissions

Problem: Maximum Subtree of the Same Color

Try to solve the Maximum Subtree of the Same Color problem.

Statement

You are given an undirected tree rooted at node 00 consisting of n nodes numbered from 00 to n −1- 1. The tree is represented by a 2extD2 ext{D} integer array edges of length n −1- 1, where edges[i] =[ui,vi]= [u_i, v_i] indicates an edge between nodes uiu_i and viv_i.

You are also given a 00 indexed integer array colors of length n, where colors[i] denotes the color assigned to node i.

A subtree rooted at a node u consists of node u and all of its descendants. A subtree is said to have the same color if every node in the subtree shares the exact same color.

Return the maximum size of a subtree where all nodes have the same color.

Constraints:

  • n ==== edges.length +1+ 1

  • 1≤1 \leq n ≤5imes104\leq 5 imes 10^4

  • edges[i] ==[ui,vi]== [u_i, v_i]

  • 0≤ui,vi<0 \leq u_i, v_i < n

  • colors.length ==== n

  • 1≤1 \leq colors[i] ≤105\leq 10^5

  • The input is generated such that the graph represented by edges is a tree.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Maximum Subtree of the Same Color

Try to solve the Maximum Subtree of the Same Color problem.

Statement

You are given an undirected tree rooted at node 00 consisting of n nodes numbered from 00 to n −1- 1. The tree is represented by a 2extD2 ext{D} integer array edges of length n −1- 1, where edges[i] =[ui,vi]= [u_i, v_i] indicates an edge between nodes uiu_i and viv_i.

You are also given a 00 indexed integer array colors of length n, where colors[i] denotes the color assigned to node i.

A subtree rooted at a node u consists of node u and all of its descendants. A subtree is said to have the same color if every node in the subtree shares the exact same color.

Return the maximum size of a subtree where all nodes have the same color.

Constraints:

  • n ==== edges.length +1+ 1

  • 1≤1 \leq n ≤5imes104\leq 5 imes 10^4

  • edges[i] ==[ui,vi]== [u_i, v_i]

  • 0≤ui,vi<0 \leq u_i, v_i < n

  • colors.length ==== n

  • 1≤1 \leq colors[i] ≤105\leq 10^5

  • The input is generated such that the graph represented by edges is a tree.