<p>There is a tree (i.e. a connected, undirected graph with no cycles) consisting of <code>n</code> nodes numbered from <code>0</code> to <code>n - 1</code> and exactly <code>n - 1</code> edges.</p>

<p>You are given a <strong>0-indexed</strong> integer array <code>vals</code> of length <code>n</code> where <code>vals[i]</code> denotes the value of the <code>i<sup>th</sup></code> node. You are also given a 2D integer array <code>edges</code> where <code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> denotes that there exists an <strong>undirected</strong> edge connecting nodes <code>a<sub>i</sub></code> and <code>b<sub>i</sub></code>.</p>

<p>A <strong>good path</strong> is a simple path that satisfies the following conditions:</p>

<ol>
	<li>The starting node and the ending node have the <strong>same</strong> value.</li>
	<li>All nodes between the starting node and the ending node have values <strong>less than or equal to</strong> the starting node (i.e. the starting node&#39;s value should be the maximum value along the path).</li>
</ol>

<p>Return <em>the number of distinct good paths</em>.</p>

<p>Note that a path and its reverse are counted as the <strong>same</strong> path. For example, <code>0 -&gt; 1</code> is considered to be the same as <code>1 -&gt; 0</code>. A single node is also considered as a valid path.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/08/04/f9caaac15b383af9115c5586779dec5.png" style="width: 400px; height: 333px;" />
<pre>
<strong>Input:</strong> vals = [1,3,2,1,3], edges = [[0,1],[0,2],[2,3],[2,4]]
<strong>Output:</strong> 6
<strong>Explanation:</strong> There are 5 good paths consisting of a single node.
There is 1 additional good path: 1 -&gt; 0 -&gt; 2 -&gt; 4.
(The reverse path 4 -&gt; 2 -&gt; 0 -&gt; 1 is treated as the same as 1 -&gt; 0 -&gt; 2 -&gt; 4.)
Note that 0 -&gt; 2 -&gt; 3 is not a good path because vals[2] &gt; vals[0].
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/08/04/149d3065ec165a71a1b9aec890776ff.png" style="width: 273px; height: 350px;" />
<pre>
<strong>Input:</strong> vals = [1,1,2,2,3], edges = [[0,1],[1,2],[2,3],[2,4]]
<strong>Output:</strong> 7
<strong>Explanation:</strong> There are 5 good paths consisting of a single node.
There are 2 additional good paths: 0 -&gt; 1 and 2 -&gt; 3.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/08/04/31705e22af3d9c0a557459bc7d1b62d.png" style="width: 100px; height: 88px;" />
<pre>
<strong>Input:</strong> vals = [1], edges = []
<strong>Output:</strong> 1
<strong>Explanation:</strong> The tree consists of only one node, so there is one good path.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == vals.length</code></li>
	<li><code>1 &lt;= n &lt;= 3 * 10<sup>4</sup></code></li>
	<li><code>0 &lt;= vals[i] &lt;= 10<sup>5</sup></code></li>
	<li><code>edges.length == n - 1</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt; n</code></li>
	<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>
	<li><code>edges</code> represents a valid tree.</li>
</ul>

class DSU{
    vector<int> parent, size;

public:

    DSU(int n){
        parent.resize(n);
        size.resize(n, 1);

        for(int i = 0; i < n; i++){
            parent[i] = i;
        }
    }

    int findUltimateParent(int node){
        if(parent[node] == node){
            return node;
        }

        return parent[node] = findUltimateParent(parent[node]);
    }


    void unionBySize(int x, int y){
        int ulp_x = findUltimateParent(x), ulp_y = findUltimateParent(y);

        if(ulp_x == ulp_y) return;

        if(size[ulp_x] > size[ulp_y]){
            // merge y into x
            parent[ulp_y] = ulp_x;
            size[ulp_x] += size[ulp_y];
        } else{
            // merge x into y
            parent[ulp_x] = ulp_y;
            size[ulp_y] += size[ulp_x];
        }
    }

    int getSize(int node){
        return size[findUltimateParent(node)];
    }
};


class Solution {
public:
    int numberOfGoodPaths(vector<int>& vals, vector<vector<int>>& edges) {
        int n = vals.size();

        vector<int> adj[n];

        // create graph


        for(auto &it: edges){
            int &x = it[0], &y = it[1];
            adj[x].push_back(y);
            adj[y].push_back(x);
        }

        map<int, vector<int>> mp; // value -> {nodes, .. }

        for(int i = 0; i < n; i++){
            mp[vals[i]].push_back(i);
        }

        DSU dsu(n);

        int ans = 0;

        // start processing the smallest node: grredy

        for(auto &[val, allNodes]: mp){
            
            // go to all neighbours and try to union them
            for(auto &node: allNodes){
                
                for(auto &nei: adj[node]){
                    if(val >= vals[nei]){
                        dsu.unionBySize(node, nei);
                    }
                }

            }

            //  process all the unions to get the count for good paths where it has same values as val
            unordered_map<int, int> mp; // to count the nodes

            for(auto &node: allNodes){
                int ulp = dsu.findUltimateParent(node);
                mp[ulp]++;
            }

            for(auto &[node, count]: mp){
                ans += (count*(count + 1))/2;
            }

        }

        return ans;

    }
};

/*
    map all the values to nodes

    i.e create map of values to node numbers

    then we will be greedy and start with smaller values and trie to connect the neighbours to its union till its values
    is less than or equal to current

    after connection we can count how many nodes ha


*/
221493