Problem

Submissions

Spltting Edges

$100\mathrm{.}0\%$

Submissions: $1+$

Points: $30$

You have been given an undirected tree with N nodes and N $-1$ edges, each node has a value values; either $1,2,$ or $3.$ When you cut an edge, the tree gets split into two components and this splitting is valid if both components satisfy the below property.

Property : Let X be the product of all the node values in the component then, X should be divisible by $6.$

In simple words, you are given an array Values which, contains the value of each node and an Edges array which contains N $-1$ undirected edges of the tree. Find the number of valid splits of the gliven tree ie$.$ number of edges that can be removed such that components formed after splitting follows the above given property.

NOTE ; You need to split the tree into two components only lie. only one edge removal is possible at once.

Input:

$N=5$

Values$[=\{3,2,2,3,1\}$

Edges

Output:

$1$

Explanation:

Input:

$]\}$

$\{0,2[1,3\}\}$

$4,6$

$\{[2,5$

$3$

Explanation:

Geek can split the tree at edge $\{0,1\}$ and the resulting two components will have product divisible by $6.$

Similarly, Geek can also split the tree at edge $\{1,4\}$ and the resulting two components will have product divisible by $6.$

Similarly, Geek can also split the tree at edge $\{0\mathrm{.}2\}$ and the resulting two components will have product divisible by $6.$