A20250305b_meesho

import java.util.*;
//A20250305b_meesho
/*


given you a tree
each node having a integer value
your task is to find the count of valid vertical paths in that tree

a path is valid

if (sum of all ancestor nodes) % m is 0



*/

/*

//important thing to be noted here is

in vertical paths only ancestor nodes and current node exist

assume this is your tree and m = 2

                1
               / \
               0  1
                  |
                  2
                  |
                  1
                  |
                  8
                  |
                  8
                  |
                  0

The valid paths (they can be subarrays or subpaths in a vertical path)
    0

    1 1

        2
    1 1 2

      1 2 1

            8
      1 2 1 8

              8
            8 8
      1 2 1 8 8

                0
              8 0
            8 8 0
      1 2 1 8 8 0

total 14 valid subpaths


this can be solved by simple dfs
to know the current valid subpaths
we just need to know how many times the same reminder came as similar to current reminder
we can add that to the whole sum

*/

/*

//inputs for m and node values and tree connections
2
1 0 1 2 1 8 8 0
8 7
0 1
0 2
2 3
3 4
4 5
5 6
6 7

expected output -
The result is 14


*/


@SuppressWarnings({"unused","unchecked"})
public class A20250305b_meesho  {

    static Scanner sc = new Scanner(System.in);

    private static int[] getArray() {
        String[] sArr = sc.nextLine().split(" ");
        int[] arr = Arrays.stream(sArr).mapToInt(Integer::parseInt).toArray();
        return arr;
    }

    private static char[] getCharArray() {
        String[] sArr = sc.nextLine().split(" ");
        char[] cArr = new char[sArr.length];
        for (int i = 0; i < sArr.length; i++) {
            cArr[i] = sArr[i].charAt(0); // Take the first character of each string
        }
        return cArr;
    }

    private static int getMax(int[] arr) {
        int currMax = Integer.MIN_VALUE;
        for (int curr : arr) {
            currMax = Math.max(currMax, curr);
        }
        return currMax;
    }

    public static void getCount(ArrayList<Integer>[] adjList,
    int[] a,int currInd,int[] visited,int[] nodeValues,HashMap<Integer,Integer> remfMap,int m){
        int currVal = nodeValues[currInd];
        a[1] += currVal; //currSum
        int currReminder = a[1] % m;
        int currFreq = remfMap.getOrDefault(currReminder,0);
        a[0] += currFreq; //storing the answer

        currFreq += 1;//adding curr to the answer
        remfMap.put(currReminder,currFreq);
        visited[currInd] = 1;
        for(int child:adjList[currInd]){
            if(visited[child]==1)
                continue;
            getCount(adjList,a,child,visited,nodeValues,remfMap,m);

        }

        visited[currInd] = 0;
        currFreq -= 1;
        remfMap.put(currReminder,currFreq);
        a[1] -= currVal;//adjusting the currSum

        return;

    }


    public static void main(String args[]) {
        // prepare the inputs

        int m = getArray()[0];
        int[] nodeValues = getArray();
        int[] tempArr = getArray();

        int nodes = tempArr[0];
        int edges = tempArr[1];
        ArrayList<Integer>[] adjList =(ArrayList<Integer>[]) new ArrayList[nodes];//explicit type conversion
        for(int i =0;i<nodes;i+=1){
            adjList[i] = new ArrayList<>();
        }
        int temp = edges;
        //fill up the graph
        while(temp!=0){
            temp-=1;
            tempArr = getArray();
            int n1 = tempArr[0];
            int n2 = tempArr[1];
            adjList[n1].add(n2);
            adjList[n2].add(n1);
        }
        int[] ans = new int[2]; //0th ind is for final answer , 1st ind is currsum
        int[] visited = new int[nodes];
        HashMap<Integer,Integer> remfMap = new HashMap<>();//to store frequency of current reminder
        remfMap.put(0,1);//default to put ,as empty subarray is a valid subarray or subpath
        getCount(adjList,ans,0,visited,nodeValues,remfMap,m);
        int res = ans[0];


        System.out.println("The result is " + res);

    }
}

class Pair{
    int row;
    int col;
    public Pair(int i,int j){
        this.row = i;
        this.col = j;

    }
}