Hard · Graphs

Number of Good Paths

Given a tree of n nodes with values vals[i] and its n − 1 undirected edges, return the number of distinct good paths: simple paths whose two endpoints hold the same value and that contain no node with a larger value. Each single node counts, and a path and its reverse count once.

Examples

Example 1

{
  "vals": [1, 3, 2, 1, 3],
  "adj": [
    [1],
    [0, 2],
    [1, 3, 4],
    [2],
    [2]
  ]
}

Output: 6 good paths

Example 2

{
  "vals": [1, 1, 1, 1],
  "adj": [
    [1],
    [0, 2],
    [1, 3],
    [2]
  ]
}

Output: 10 good paths

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.