Special Paths :
Difficulty Level : Medium
Submissions : 490
Asked In :
Marks :15
: 16 | : 1
You are given the following:
- A Tree with $$$n$$$ nodes
- An array $$$A$$$ denoting the value of each node
- All nodes in the path are traversed exactly once.
- The value of starting node and terminating node in the path is same and $$$starting \hspace{3pt} node \neq terminating \hspace{3pt} node$$$.
- The values of any node in the path are not greater than the value of starting node.
Count the number of special paths in the tree.
Note: Two paths are different if they contain at least one different node.
The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^4)$$$ — the number of test cases. The description of $$$t$$$ testcase follows.
The first line of each test case contains a single integer $$$n$$$ — the number of vertices in the tree $$$(2 \le n \le 10^5)$$$.
The second line contains $$$n$$$ space separated integers $$$a_1,a_2,...a_n$$$ $$$(1 \le a_i \le 10^9)$$$ denoting the values of the nodes of the tree.
The next $$$n-1$$$ lines describe the tree. Each contains two space separated integers $$$u$$$ and $$$v$$$ $$$(1 \le u, v \le n; $$$ $$$u \neq v \hspace{1 pt};)$$$ denoting an edge between vertices $$$u$$$ and $$$v$$$. It is guaranteed that these edges form a tree.
It is guaranteed that the sums of $$$n$$$ and $$$q$$$ over all test cases do not exceed $$$10^5$$$ individually.
For each test case, print the count of special paths in the tree in a new line.
452 3 1 2 31 21 33 43 562 3 1 2 3 31 21 33 43 52 653 3 2 3 32 13 24 25 351 3 1 2 32 13 14 15 1
2 4 6 2
In sample test case 1, The following paths are special paths:
- Path $$$1(2)\to 3(1)\to 4(2)$$$
- Path $$$2(3)\to 1(2)\to 3(1)\to 5(3)$$$
In sample test case 2, The following paths are special paths:
- Path $$$1(2) \to 3(1) \to 4(2)$$$
- Path $$$2(3) \to 1(2) \to 3(1) \to 5(3)$$$
- Path $$$6(3) \to 2(3)$$$
- Path $$$6(3) \to 2(3) \to 1(2) \to 3(1) \to 5(3)$$$
